레이팅 미적용베시는 카우랜드로 여행을 떠난다. 카우랜드에는 \(1\)부터 \(N\)까지 번호가 붙은 \(N\) (\(2\le N\le 2\cdot 10^5\))개의 마을과 \(M\) (\(1\le M\le 4\cdot 10^5\))개의 일방통행 도로가 있다. \(i\)번째 도로는 마을 \(a_i\)에서 마을 \(b_i\)로 이어지며 라벨 \(l_i\)를 가진다 (\(1\le a_i,b_i\le N\), \(1\le l_i\le 10^9\)).
마을 \(x_0\)에서 시작하는 길이 \(k\)의 여행은 마을들의 수열 \(x_0, x_1, \ldots, x_k\)로, 모든 \(0\le i < k\)에 대해 마을 \(x_i\)에서 마을 \(x_{i+1}\)로 가는 도로가 존재하는 것을 말한다. 카우랜드에는 길이가 무한한 여행이 없고, 같은 마을 쌍을 연결하는 도로가 두 개 존재하지 않음이 보장된다.
각 마을에 대해, 베시는 그 마을에서 시작하는 가장 긴 여행을 알고 싶어 한다. 어떤 시작 마을에서는 가장 긴 여행이 여러 개 있을 수 있는데, 그중에서 베시는 도로 라벨의 수열이 사전순으로 최소인 여행을 선호한다. 같은 길이의 두 수열이 있을 때, 처음으로 서로 달라지는 위치에서 첫 번째 수열의 원소가 두 번째 수열의 원소보다 작으면 첫 번째 수열이 사전순으로 더 작다고 한다.
각 마을에서 시작하는 베시가 선호하는 여행의 길이와 도로 라벨의 합을 출력하라.
문제 제공: Claire Zhang, Spencer Compton
채점 방식
- 입력 5-6: 모든 라벨이 같다.
- 입력 7-8: 모든 라벨이 서로 다르다.
- 입력 9-10: \(N,M\le 5000\)
- 입력 11-20: 추가 제약 조건 없음.
문제 제공: Claire Zhang, Spencer Compton
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 세 정수 \(a_i\), \(b_i\), \(l_i\)가 주어지며, 이는 \(a_i\)에서 \(b_i\)로 가는 라벨 \(l_i\)의 도로를 나타낸다.
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 마을 \(i\)에서 시작하는 베시가 선호하는 여행의 길이와 도로 라벨의 합을 공백으로 구분하여 출력한다.
4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 100 0
1 10
1 10
2 204 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 10 0
1 10
1 5
2 12In the following explanation, we let \(a_i\overset{l_i}\to b_i\) represent the
road from \(a_i\) to \(b_i\) with label \(l_i\).
There are several trips starting from vertex \(4\), including
\(4 \overset{4}\to 3\overset{5}\to 1\), \(4\overset{1}\to 1\), and
\(4\overset{2}\to 2\overset{10}\to 1\). Of these trips,
\(4 \overset{4}\to 3\overset{5}\to 1\) and \(4\overset{2}\to 2\overset{10}\to 1\)
are the longest. These trips each have length 2, and their road label sequences
are \([4,5]\) and \([2,10]\), respectively. \([2,10]\) is the lexicographically
smaller sequence, and its sum is \(12\).
4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 10 0
1 10
1 5
2 74 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 10 0
1 5
1 10
2 7riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Gold