BOJ 19558 Joker

BOI 2020 #C Joker

 

 

오랜만에 글을 쓴다.

 

 

 

Summary

 

그래프가 주어진다. ($1 <= N, M <= 200000$)

"$[L_i, R_i]$ 구간의 간선을 전부 삭제했을 때, 남은 그래프가 이분 그래프가 되는지 판별하여라." 라는 쿼리가 $Q$개 주어진다. ($1 <= Q <= 200000$)

 

 

 

Solution

 

고정된 $i$에 대해서, $[i, P_i]$ 구간의 간선을 전부 삭제했을 때 남은 그래프가 이분 그래프가 되는 최소의 $P_i$를 찾자. 모든 $i$에 대해 $P_i$를 전부 전처리한다면, 각 쿼리를 O(1)에 처리할 수 있다.

 

우선, $P_i$는 $i$가 증가함에 따라 단조증가한다는 관찰을 할 수 있다.

"$i$에 대한 Optimal한 $P_i$가 단조증가한다"라는 것은 Divide and Conquer Optimization으로 관리할 수 있다는 뜻이다.

$f(L, R, L_{opt}, R_{opt})$를 $[L, R]$ 구간의 $i$에 대하여 $P_i$가 $[L_{opt}, R_{opt}]$에 존재함이 보장될 때, $P_i$를 전부 구하는 함수라고 하자. $M = (L+R)/2$에 대하여, $P_M$을 $R_{opt}-L_{opt}$회의 Union&Find 연산에 구할 수 있다. 그 후, $f(L, M-1, L_{opt}, P_M)$, $f(M+1, R, P_M, R_{opt})$를 호출해주면 된다.

 

주의할 점은 $f(L, R, L_{opt}, R_{opt})$를 호출했을 떄, $[1, L)$ 구간과 $(R_{opt}, M]$ 구간의 간선들은 이미 Union이 되어 있어야 한다. 함수를 호출하기 전에 아직 Union이 되어있지 않은 구간을 Union해주고, 빠져나올 때 Rollback해주면 시간복잡도를 해치지 않고 구현할 수 있다.

 

총 시간복잡도는 $O((N+M)log^2N + Q)$이다.

 

 

 

Sample Code

 

구현이 깔끔하진 않다.

http://boj.kr/88351ec2a740463692062098653a2ab7

 

 

 

Further Approach

 

비슷한 풀이를 사용하는 문제로는 NOI(China) 2014 Enchanted Forest, Hello, BOJ 2023! 정밀지도 제작, SNUPC 2020 직선형 분자 만들기 등이 있다. 각각 서로 다른 관찰들이 필요하기 때문에, 관심이 있다면 한번 풀어보자.