레이팅 미적용개발팀 '리세'는 \(N\)개의 작업으로 이루어진 프로젝트를 수행한다. 작업 \(i\)는 \(d_i\)의 시간이 걸린다. \(M\)개의 선후 관계 \((u, v)\)는 작업 \(u\)가 완전히 끝난 뒤에야 작업 \(v\)를 시작할 수 있음을 의미한다. 선후 관계에 사이클이 없다면 작업을 병렬로 최대한 활용할 수 있다.
각 작업 \(i\)에 대해, 시점 \(0\)으로부터 작업 \(i\)가 최대한 빨리 완료될 수 있는 시각을 구하여라. 선후 관계에 사이클이 있으면 \(-1\)을 출력한다.
모든 작업은 선행 작업이 끝나는 즉시 동시에 시작할 수 있다 (무한한 병렬 실행 가능).
- \(1 \le N \le 200\,000\)
- \(0 \le M \le 300\,000\)
- \(1 \le d_i \le 10^6\)
- \(1 \le u, v \le N\), \(u \ne v\)
- 같은 선후 관계가 중복 입력될 수 있다.
첫째 줄에 작업의 수 \(N\)과 선후 관계의 수 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 각 작업의 소요 시간 \(d_1, d_2, \ldots, d_N\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 선후 관계 \(u\), \(v\)가 공백으로 구분되어 주어진다.
사이클이 없으면 \(N\)개의 줄에 걸쳐, \(i\)번째 줄에 작업 \(i\)의 최조 완료 시각을 출력한다. 사이클이 있으면 \(-1\)을 출력한다.
3 2
3 2 4
2 3
1 2
3
5
9
작업 \(1\)은 시간 \(3\)에 완료. 작업 \(2\)는 \(1\) 완료 후 시작: \(3 + 2 = 5\)에 완료. 작업 \(3\)은 \(5 + 4 = 9\)에 완료.
4 4
5 3 7 2
2 4
1 2
1 3
3 4
5
8
12
14
\(1\)(\(5\))→\(2\): 완료 \(8\), \(1\)(\(5\))→\(3\): 완료 \(12\). 작업 \(4\)는 \(2\)와 \(3\) 모두 끝나야 하므로 \(12 + 2 = 14\). 임계 경로: \(1 \to 3 \to 4\).
riseoj 작성
출처 Original