JOI 2012 final round #5 - JOI 국가의 행사

BOJ 링크

내가 아는 풀이만 3개다. 3개 다 멋진 풀이라서 공유하기로 한다.

3개 풀이 모두 다익스트라 전처리가 필요하다. 대신 시작 정점이 축제가 열리는 K개의 정점 모두다!

다익스트라는 시작 정점이 꼭 하나일 필요가 없다. 납득이 가지 않는다면 시작 정점들을 모두 하나의 큰 정점으로 연결한다고 생각해 보자. 시작 정점이 1개인 다익스트라로 바뀐다.

구현도 간단하다. 맨 처음 heap에 (cost = 0, vertex = 시작 정점)을 넣을 때 K개를 다 넣고 일반적인 다익스트라를 돌리면 된다.

이 과정이 끝나면 모든 정점 \(v\)에 대해 축제가 열리는 정점까지의 최단거리인 \(d[v]\)를 얻는다.

이제 쿼리를 오프라인으로 처리할 건데, 처리 방법이 3개의 풀이에서 모두 조금씩 다르다.

1. Set merging : \(Q\lg ^2Q + E \alpha (V)\)

각각의 정점에 대해 쿼리를 의미하는 set U를 관리하자.

k번째 쿼리가 (s,e)의 형태로 들어왔다면 U[s]와 U[e]에 k를 넣어 주는 방식이다.

이제 Union-find를 이용하여 정점과 이 set들을 merge한다!

정점을 가중치 d가 큰 순서대로 정렬하고, 자기보다 가중치가 큰 정점과 연결된 간선만 사용하면서 union-find merge해 준다.

만약 uf-merge 하는 두 정점의 컴포넌트가 다를 경우 두 정점의 U를 merge해 주는데, 작은 쪽을 큰 쪽으로 merge해야 \(Q \lg ^2 Q\) 시간복잡도가 보장된다. 작은 쪽을 U[S], 큰 쪽을 U[B]라고 하자.

U[S]의 원소(query) k 중

U[B]에도 k가 있을 경우 : 해당 쿼리에 대한 답이 d[v]가 된다. (d[v]는 현재 정점) 따라서 ans[k] = d[v]로 설정한 뒤 U[B]에서 k를 뺀다.

없을 경우 : U[B]에 k를 넣는다.

만약 set을 unordered_set으로 대체하면 이론적으로 복잡도가 \(Q \lg Q\)가 되지만, 어차피 set을 쓰는 시점에서 실질적으로 \(\text{set}(Q) \sim \lg ^2 Q\)라 큰 의미가 없다...

(comment) 풀이를 설명하려고 코드를 보다 보니 구현 실수가 있었다. 작은 set을 큰 set에 merge하지 않은 것! 뭐 이런 문제 특성상 데이터를 빡세게 만들기 어려워서 그런지 AC는 나더라... 아직 구현이 완숙하지 않다.

2. Parallel Binary Search : \(Q\lg Q + E \alpha (V) \lg Q\)

어쩌면 세 풀이 중 가장 technical한 풀이가 되겠다.

아이디어는 간단하다. Q개의 쿼리에 대해서 parallel binary search를 한다. pbs에 대해서는 jason9319님의 설명을 참조하자. 간단히 설명하자면, 원래 [lo, hi]를 관리하던 걸 [lo[0], hi[0]], ... , [lo[Q-1], hi[Q-1]]을 관리하는 걸로 문제를 바꿨다고 생각하면 된다.

PBS를 한 번 돌릴 때마다 Union-find를 계속 simulate한다. 체크할 쿼리가 있는 시점에 멈춰서 두 정점이 연결되어 있는지를 체크해주면 된다.

3. Union-find Tree + LCA : \(Q\lg V + E\lg V\)

이 풀이는 무려 online이다! 갓풀이가 그렇듯 약간의 테크닉 + 쩌는 관찰로 구성되어 있다.

union-find를 할 때 실제로 merge를 수행하는 간선은 MST에 사용되는 N-1개 뿐이다.

똑같이 uf tree를 만드는데, 정점의 가중치는 무조건 부모 노드 > 자식 노드이도록 merge해주는 거다. 

즉, rank compression 없이 path compression만 사용한다. path나 rank 중 하나만 해도 \(\lg V\) 시간복잡도가 보장된다고 한다. 개꿀!

이제 쿼리 s,e가 들어오면 만들어둔 트리에서의 LCA(s,e)의 가중치가 답이 된다.