레이팅 미적용농부 존의 농장에는 \(1\dots N\)으로 번호가 붙은 \(N\) (\(1\le N\le 2\cdot 10^5\))마리의 소가 있으며, 각 소는 자신만의 축사에서 산다. 각 소 \(i\)에게는 가장 친한 친구 \(a_i\) (\(1\le a_i\le N\))가 있다. 소는 자기 자신과 가장 친한 친구일 수 있고, 여러 소가 같은 소를 가장 친한 친구로 가질 수도 있다. 소들은 파티를 좋아해서, \(M\) (\(1\le M\le 2\cdot 10^5\))일 밤 연속으로 파티를 열기로 했다.
\(i\)번째 밤에, 소 \(c_i\)는 자신의 축사에서 유형 \(t_i\)의 파티를 열기로 결정한다. 여기서 \(t_i\in \texttt{"COW"}\)이다. 이 파티는 소 \(c_i\)가 다른 유형의 파티를 열기로 결정할 때까지 이후의 모든 밤에도 계속 존재한다.
매일 밤, 각 소는 파티에 가려고 시도한다. 파티를 열고 있지 않은 소는 가장 친한 친구의 축사를 확인하고, 그곳에 파티가 없으면 가장 친한 친구가 가는 곳으로 따라간다 (그 친구 역시 자신의 가장 친한 친구를 따라갈 수 있으며, 이런 식으로 계속된다). 소가 끝내 파티를 찾지 못하고 그날 밤을 포기하는 경우도 있을 수 있다.
각 밤에 대해, 유형 \(C\), \(O\), \(W\)의 파티에 도착하게 되는 소의 수를 각각 계산하라.
Problem credits: Benjamin Qi
SCORING
- 입력 2: \(N, M\leq 100\)
- 입력 3-4: \(N, M\leq 4000\)
- 입력 5-9: \(\{a_i\}\)는 \(\{1,\dots, N\}\)의 순열이다
- 입력 10-21: 추가 제약 없음
Problem credits: Benjamin Qi
첫째 줄에 소의 수 \(N\)이 주어진다.
둘째 줄에 \(a_1,\dots, a_N\)이 주어지며, \(a_i\)는 소 \(i\)의 가장 친한 친구이다.
셋째 줄에 밤의 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 정수 \(c_i\) (\(1\le c_i\le N\))와 문자 \(v_i\)가 주어지며, 각각 파티를 여는 소와 파티의 유형을 나타낸다.
\(M\)개의 줄을 출력하며, \(i\)번째 줄에는 공백으로 구분된 세 정수, 즉 \(i\)번째 밤에 유형 \(C\), \(O\), \(W\)의 파티에 가는 소의 수를 각각 출력한다.
5
2 3 4 5 4
4
2 C
4 C
4 W
2 O2 0 0
5 0 0
2 0 3
0 2 3On night \(1\), there is only one party of type \(C\) at barn \(2\), which only cows
\(1\) and \(2\) attend.
On night \(2\), there is a new party of type \(C\) at barn \(4\), which cows \(3\), \(4\),
and \(5\) can now reach.
On night \(3\), the party at barn \(4\) is changed to type \(W\), affecting cows \(3\),
\(4\) and \(5\).
On night \(4\), the party at barn \(2\) is changed to type \(O\), affecting cows \(1\)
and \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Gold