레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 두 배인 4초이다.*
베시는 휴가 중이다! 최근의 기술 발전 덕분에 베시는 시간 여행까지 가능한 첨단 항공편으로 여행한다. 게다가 두 "평행" 버전의 베시가 만나더라도 아무 문제가 없다.
이 나라에는 \(1, 2, \ldots, N\)으로 번호가 매겨진 공항 \(N\)개와 시간 여행 항공편 \(M\)개가 있다 (\(1\leq N, M \leq 200000\)). 항공편 \(j\)는 시각 \(r_j\)에 공항 \(c_j\)를 떠나 시각 \(s_j\)에 공항 \(d_j\)에 도착한다 (\(0 \leq r_j, s_j \leq 10^9\), \(s_j < r_j\)일 수도 있다). 또한 베시는 공항 \(i\)에서 환승 시간 \(a_i\) (\(1\le a_i\le 10^9\))를 확보해야 한다. (즉, 베시가 시각 \(s\)에 공항 \(i\)에 도착하는 항공편을 탔다면, \(r \geq s + a_i\)인 시각 \(r\)에 그 공항을 떠나는 항공편으로 갈아탈 수 있다. 환승 시간은 베시가 공항에 도착하는 시각에는 영향을 주지 않는다.)
베시는 시각 \(0\)에 도시 \(1\)에서 출발한다. \(1\)부터 \(N\)까지의 각 공항에 대해, 베시가 그 공항에 도착할 수 있는 가장 이른 시각은 언제인가?
출제자: Brandon Wang
배점
- 입력 3-5: 모든 \(j\)에 대해 \(r_j < s_j\), 즉 모든 항공편은 출발한 후에 도착한다.
- 입력 6-10: \(N, M \leq 5000\)
- 입력 11-20: 추가 제약이 없다.
출제자: Brandon Wang
입력의 첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에 항공편이 주어진다. 이 중 \(j\)번째 줄에는 \(c_j\), \(r_j\), \(d_j\), \(s_j\)가 순서대로 주어진다. (\(1\leq c_j, d_j \leq N\), \(0\leq r_j, s_j \leq 10^9\))
다음 줄에 공항 정보가 주어진다. 공백으로 구분된 \(N\)개의 정수 \(a_1, \ldots, a_N\)이 주어진다.
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 베시가 공항 \(i\)에 도착할 수 있는 가장 이른 시각을 출력하고, 그 공항에 도착하는 것이 불가능하면 -1을 출력한다.
3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 100
0
20Bessie can take the 3 flights in the listed order, which allows her to arrive at
airports 1 and 2 at time 0, and airport 3 at time 20.
Note that this route passes through airport 2 twice, first from time 10-11 and
then from time 0-1.
3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 100
10
-1In this case, Bessie can take flight 1, arriving at airport 2 at time 10.
However, she does not arrive in time to also take flight 2, since the departure
time is 10 and she cannot make a 1 time-unit layover.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Silver