Thursday, July 9, 2015

Croatian Olympiad in Informatics 2009 OTOCI

문제 링크(Problem Link)

주어진 쿼리를 수행하다보면 최종 그래프의 형태가 Forest가 된다. 따라서 Heavy-Light Decomposition이나 Link-Cut Tree로 그래프를 모델링하여 각 쿼리마다 수행되는 시간을 줄여볼 수 있다.

그런데 나는 조금 다르게 접근하여 보다 쉽게 풀었다. 우선 쿼리를 다 저장하여두고, 최종 그래프가 어떤 형태인지 알아낸다. 거기서 각 트리마다 dfs를 순회하면서 chain을 표시하고, 인접한 chain의 정점들은 다 연속한 번호를 가지도록 각 정점을 renumbering한다.(dfs 순회 중 start number로 numbering했는데 finish number로 해도 될 듯) 이렇게 함으로써 나중에 두 정점 사이의 거리를 계산할 때, 한 chain마다 log 시간에 한 번에 구할 수 있다.

이제 쿼리를 순서대로 다시 보면서 각 연산들을 한다.
bridge - O(log*N) : union-find. 
penguins - O(log N) : update the binary indexed tree. 
excursion - O(log^2 N) : 두 노드 A, B 사이의 팽귄 수를 구한다고 가정하면
chain(X) : X가 속한 chain
depth(X) : X가 속한 트리에서 X의 depth
first(chain(X)) : X가 속한 chain의 depth가 가장 작은 노드
parent(X) : X의 부모 노드
chain(X).count(Y, Z) : X가 속한 chain에서 Y와 Z 사이의 거리

output = 0
while chain(A) ≠ chain(B):
if depth(first(chain(A))) < depth(first(chain(B))):
  swap A and B
output = output + chain(A).count(first(chain(A)), A)
A = parent(first(chain(A)))
output = output + chain(A).count(A, B)

따라서 최종적으로 O(N log N + Q log^2 N).

소스 코드(Source Code)

No comments:

Post a Comment