Codeforces Round #808 (Div. 1)

https://codeforces.com/contest/1707

 

A. Doremy's IQ

 

뒤에서부터 그리디하게 하면 된다.

 

B. Difference Array

 

a_n의 합이 5e5 밖에 안된다.

-> 문제에서 주어진 operation을 하다보면 0이 존나 많이 생긴다는 것을 알 수 있다.

따라서 0만 적당히 처리해주고 나머지 부분에 대해서는 그냥 sort를 박으면 된다.

 

C. DFS Trees

 

어떤 u - v 간선이 MST에 속하지 않는다고 가정하자.

그렇다면 u가 root일 때 v의 subtree와 v가 root일 때 u의 subtree를 제외한 나머지는 불가능하다.

하지만 시간 복잡도상 u가 root인 그래프와 v가 root인 그래프를 실제로 저장할 수는 없다.

따라서 0이 root인 그래프를 만들어주고 적당히 처리해주면 된다.

만일 u와 v 사이에 상하관계가 없다면, u의 subtree와 v의 subtree를 제외한 모두를 불가능하게 해주면 되니 ok.

하지만 u와 v 사이에 상하관계가 있다면 (u가 v의 조상)

(u - v 경로 상에 존재하는 u의 child) 부터 (v의 parent)까지 불가능하게 만들어주어야 한다.

신기한 dfs 테크닉으로 이것을 이룰 수 있다.dfs를 타고 내려가면서 point라는 것을 저장하자. (point는 cur 다음에 오는 노드를 의미한다)그렇다면 u -> point[u] -> point[point[u]] -> ... -> v의 경로로 dfs에서 v에 도착하였을 것이다.그러므로 point[u]에서 par[v] 까지를 불가능하게 만들어주면 된다.unable[point[u]]++, unable[v] -- 를 해주면 된다.이제 이를 prefix sum 느낌으로 spread해주면 된다.

https://codeforces.com/contest/1707/submission/164685439