사용자 도구

사이트 도구


ps:problems:boj:2927

남극 탐험

ps
링크https://www.acmicpc.net/problem/2927
출처BOJ
문제 번호2927
문제명남극 탐험
레벨다이아몬드 5
분류

경로 쿼리, 동적 연결성

시간복잡도O(n+qlog^2(n))
인풋사이즈n<=30,000, q<=300,000
사용한 언어Python
제출기록158620KB / 5768ms
최고기록5768ms
해결날짜2021/05/28

풀이

  • 동적 연결성 문제와 경로 합 쿼리를 합쳐놓은 문제
  • 엣지를 추가해나가면서 어떤 두 노드가 연결되어있는지를 체크하는 것은 동적 연결성 에서 설명했듯, Disjoint Set을 사용해서 처리 가능하다.
  • 경로 합 쿼리는 Heavy Light Decomposition을 비롯, 여러가지 방법으로 풀이가 가능하다.
  • 문제는 Heavy Light Decomposition을 쓰려면 우선 트리의 구조를 알고 있어야 하는데 그것이 불가능하다는 점.
  • 그것을 오프라인 쿼리 방식으로 해결한다. 먼저 쿼리를 죽 훑으면서 엣지를 추가하는 쿼리들만 처리해본다. 이렇게 해서 만들어진 트리가 최종 트리의 모습이 될 것이므로, 이 트리를 가지고 Heavy Light Decomposition을 돌린다.
    • 이때 최종 상태가 전체가 연결된 tree가 된다는 보장은 없다. forest가 될 수도 있고, 이 경우에는 dfs 한번으로 전체를 훑을수 없다. forest안의 각 tree들에 대해서 따로 Heavy Light Decomposition를 돌릴수도 있겠지만.. 그냥 엣지들을 추가해서 하나의 트리로 합쳐버리는 것이 좀더 구현이 편해 보인다.
  • 이렇게 hld 준비가 끝나면, 아까 사용했던 Disjoint Set을 초기화하고, 다시 쿼리를 처음부터 진행하면서 처리해주면 된다.
    • 엣지 추가와 연결성 체크는 Disjoint Set을 사용해서 O(α(n)), 펭귄수 업데이트와, 경로안의 펭귄수 계산은 HLD와 펜윅트리를 사용해서 O(log^2(n)) 이 걸린다.
  • HLD를 준비하는데에 O(n), 펜윅트리를 초기화하는데에도 O(n). 각 쿼리에 대해서는 최대 O(log^2(n)) 이 걸리므로, 총 시간복잡도는 O(n+qlog^2(n)).

코드

토론

댓글을 입력하세요:
U F᠎ L H E
 
ps/problems/boj/2927.txt · 마지막으로 수정됨: 2021/05/28 16:02 저자 teferi