레이팅 미적용베시는 지난 \(M\)일(\(2 \le M \le 10^9\)) 동안 \(N\)번의 착유 세션(\(1\le N\le 10^5\))에 참석했다. 그러나 각 세션에 언제 참석했는지 기억하는 데 어려움을 겪고 있다.
각 세션 \(i = 1 \ldots N\)에 대해, 그 세션이 \(S_i\)일(\(1\le S_i\le M\))보다 이르지 않게 일어났다는 것은 알고 있다. 추가로 베시에게는 \(C\)개의 기억(\(1\le C\le 10^5\))이 있는데, 각각은 세 값의 쌍 \((a,b,x)\)로 표현되며, 세션 \(b\)가 세션 \(a\)로부터 적어도 \(x\)일 후에 일어났다는 것을 기억한다는 의미이다.
각 착유 세션이 일어날 수 있는 가장 이른 날짜를 계산하여 베시를 도와주자. 베시의 기억이 잘못되지 않았음이 보장된다. 즉, 그녀의 기억에서 나온 모든 제약을 만족하도록 세션들을 \(1\ldots M\) 범위의 날짜에 배정하는 방법이 존재한다.
문제 제공: Mark Gordon
배점
- 테스트 케이스 2-4는 \(N,C \le 10^3\)을 만족한다.
- 테스트 케이스 5-10은 추가 제약이 없다.
문제 제공: Mark Gordon
입력의 첫째 줄에 \(N\), \(M\), \(C\)가 주어진다.
다음 줄에 공백으로 구분된 \(N\)개의 정수 \(S_1,S_2,\ldots, S_N\)이 주어진다. 각 값은 \(1 \ldots M\) 범위이다.
다음 \(C\)개의 줄에 세션 \(b\)가 세션 \(a\)로부터 적어도 \(x\)일 후에 일어났음을 나타내는 세 정수 \(a\), \(b\), \(x\)가 주어진다. 각 줄에서 \(a \neq b\)이고, \(a\)와 \(b\)는 \(1 \ldots N\) 범위이며, \(x\)는 \(1 \ldots M\) 범위이다.
각 세션이 일어날 수 있는 가장 이른 날짜를 \(N\)개의 줄에 출력한다.
timeline.in · 출력을 쓸 파일 timeline.out4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 41
6
3
8Session two occurred at least five days after session one, so it cannot have
occurred before day \(1+5=6.\) Session four occurred at least two days after session
two, so it cannot have occurred before day \(6+2=8\).
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Gold