editorial

solution code

---

D

Couldn’t understand the editorial even tried to read it for more than 4 hours.

I found someone’s excellent editorial while reading the comments.

summary:

There is some quests should be cleared. There are dependencies like $(a_i,b_i)$ that means the $b_i$-th quest can only be completed after the $a_i$-th quest.

I want to know the minimum number of (clear time of the last quest - clear time of the first quest).

solution:

먼저 dependency가 없는 퀘스트 중 가장 작은 $h_i$를 가지고 있는 것을 가장 먼저 클리어한다고 생각하면, 위상 정렬로 모든 퀘스트의 끝나는 시간을 구할 수 있다.

하지만 다른 퀘스트(dependency가 없는)를 먼저 클리어 할 때가 더 이득인 경우(4번째 test case 같은 경우)를 고려해야 한다.

시작 시간을 다르게 해서 퀘스트를 다 클리어하는 데 걸리는 최솟값을 구하기 위해 $h$값의 오름차순으로 dependency가 없는 노드들을 정렬한다.

순서대로 끝나는 시간에 $k$를 더한다. 그러면 현재 고려하는 퀘스트의 종료 시간 변화로 인해 바뀌는 퀘스트들의 종료 시간을 계산하고, 가장 늦은 퀘스트 종료 시간을 구하면 된다.