레이팅 미적용베시(Bessie)의 \(N\)마리 (\(2\le N\le 10^5\)) 소 친구들(편의상 \(1\ldots N\)으로 번호가 붙어 있다)은 각자 자기 농장을 가지고 있다. 각 \(1\le i\le N\)에 대해, 친구 \(i\)는 친구 \(a_i\) (\(a_i\neq i\))를 방문하고 싶어 한다.
\(1\ldots N\)의 순열 \((p_1,p_2,\ldots, p_N)\)이 주어지면, 방문은 다음과 같이 이루어진다.
\(i\)를 \(1\)부터 \(N\)까지 차례로 보면서:
- 친구 \(a_{p_i}\)가 이미 자기 농장을 떠났다면, 친구 \(p_i\)는 자기 농장에 남는다.
- 그렇지 않다면, 친구 \(p_i\)는 자기 농장을 떠나 친구 \(a_{p_i}\)의 농장을 방문한다. 이 방문에서 기쁨의 "음머" 소리가 \(v_{p_i}\)번 (\(0\le v_{p_i}\le 10^9\)) 울려 퍼진다.
가능한 모든 순열 \(p\)에 대해, 모든 방문이 끝난 후 울린 음머 소리 횟수의 최댓값을 계산하시오.
문제 제공: Benjamin Qi and Michael Cao
배점
- 테스트 케이스 2-3은 모든 \(i\neq j\)에 대해 \(a_i\neq a_j\)를 만족한다.
- 테스트 케이스 4-7은 \(N\le 10^3\)을 만족한다.
- 테스트 케이스 8-11은 추가 제약이 없다.
문제 제공: Benjamin Qi and Michael Cao
첫째 줄에 \(N\)이 주어진다.
각 \(1\le i\le N\)에 대해, \(i+1\)번째 줄에 공백으로 구분된 두 정수 \(a_i\)와 \(v_i\)가 주어진다.
답을 나타내는 정수 하나를 출력한다.
이 문제에서 다루는 정수는 크기가 커서 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
4
2 10
3 20
4 30
1 4090If \(p=(1,4,3,2)\) then
- Buddy \(1\) visits buddy \(2\)'s farm, resulting in \(10\) moos.
- Buddy \(4\) sees that buddy \(1\) has already departed, so nothing happens.
- Buddy \(3\) visits buddy \(4\)'s farm, adding \(30\) moos.
- Buddy \(2\) sees that buddy \(3\) has already departed, so nothing happens.
This gives a total of \(10+30=40\) moos.
On the other hand, if \(p=(2,3,4,1)\) then
- Buddy \(2\) visits buddy \(3\)'s farm, causing \(20\) moos.
- Buddy \(3\) visits buddy \(4\)'s farm, causing \(30\) moos.
- Buddy \(4\) visits buddy \(1\)'s farm, causing \(40\) moos.
- Buddy \(1\) sees that buddy \(2\) has already departed, so nothing happens.
This gives \(20+30+40=90\) total moos. It can be shown that
this is the maximum possible amount after all visits, over all
permutations \(p\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Silver