기본적으로 쿼리를 순서대로 읽으며 서로소 집합을 갱신해가면서 만약 불가능한 경우에는 표시를 해둡니다.

그러면서 정보가 주어진 a, b 사이에는 양방향 간선을 할당하여 그래프를 구성하였습니다.

그런 다음 가능한 Forest를 이루는 한 정점에서 dfs를 수행하여 같은 cc안의 정점들간 상대 무게를 계산하고

저장한 쿼리를 순회하면서 출력하였습니다.


모든 과정이 O(N)에 이뤄지는 것 같은데 시간초과가 뜨네요 ㅠㅠ

단순한 상수 시간의 문제일까요? 어떻게 더 좋아질 수 있을지 잘 모르겠네요.


고수님들의 도움 부탁드립니다.

세상에 dfs에서 V[cur] = cur을 하고 있습니다. 죄송합니다 ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.