레이팅 미적용농부 존의 소들은 매일 아침 외양간을 나서기 전에 스스로 정렬하라는 그의 일상적인 요구에 지쳐 버렸다. 소들은 마침 양자물리학 박사 과정을 막 마쳤고, 일을 좀 더 빠르게 처리할 준비가 되어 있다.
오늘 아침에도 여느 때처럼 편의상 \(1 \dots N\)로 번호가 붙은 농부 존의 소 \(N\)마리(\(1 \leq N \leq 10^5\))가 역시 \(1 \dots N\)로 번호가 붙은 외양간 안의 \(N\)개의 서로 다른 위치에 흩어져 있으며, 소 \(i\)는 위치 \(p_i\)에 있다. 그런데 오늘 아침에는 \(1 \dots M\)로 번호가 붙은 \(M\)개의 웜홀(\(1 \leq M \leq 10^5\))도 있다. 웜홀 \(i\)는 위치 \(a_i\)와 위치 \(b_i\)를 양방향으로 연결하며, 너비 \(w_i\)를 가진다(\(1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9\)).
언제든지 웜홀의 양 끝에 있는 두 소는 웜홀을 통해 동시에 자리를 맞바꾸기로 할 수 있다. 소들은 \(1 \leq i \leq N\)에 대해 소 \(i\)가 위치 \(i\)에 올 때까지 이러한 맞바꾸기를 수행해야 한다.
소들은 웜홀에 짓눌리고 싶지 않다. 정렬을 위해 사용해야 하는 웜홀 중 가장 좁은 웜홀의 너비를 최대화하도록 도와주자. 소들이 스스로 정렬하는 것이 가능함이 보장된다.
문제 제공: Dhruv Rohatgi
점수 배점
- 테스트 케이스 3-5는 \(N,M\le 1000\)을 만족한다.
- 테스트 케이스 6-10은 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 두 정수 \(N\)과 \(M\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(p_1, p_2, \dots, p_N\)이 주어진다. \(p\)는 \(1\ldots N\)의 순열임이 보장된다.
\(1\) 이상 \(M\) 이하의 각 \(i\)에 대해, \(i+2\)번째 줄에 정수 \(a_i\), \(b_i\), \(w_i\)가 주어진다.
정수 하나를 출력한다. 정렬 과정에서 소가 비집고 들어가야 하는 웜홀들 중 최소 너비의 최댓값이다. 소들이 정렬하는 데 웜홀이 전혀 필요 없다면 \(-1\)을 출력한다.
wormsort.in · 출력을 쓸 파일 wormsort.out4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 39Here is one possible way to sort the cows using only wormholes of width at least
9:
- Cow 1 and cow 2 swap positions using the third wormhole.
- Cow 1 and cow 3 swap positions using the first wormhole.
- Cow 2 and cow 3 swap positions using the third wormhole.
4 1
1 2 3 4
4 2 13-1No wormholes are needed to sort the cows.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > January > Silver