COW Traversals
플래티넘 II의견: 0
There are \(N\) (\(1\le N\le 2\cdot 10^5\)) cows labeled \(1\dots N\) on Farmer John's farm, where each
cow lives in its own barn. Each cow \(i\) has a best friend \(a_i\)
(\(1\le a_i\le N\)). Cows can be best friends with themselves, and multiple cows
can have the same best friend. The cows love to party, so they have decided to
throw a party for \(M\) (\(1\le M\le 2\cdot 10^5\)) consecutive nights.
On night \(i\), cow \(c_i\) will decide to throw a party of type \(t_i\) at its barn,
where \(t_i\in \texttt{"COW"}\). This party will exist for all future nights as
well, until cow \(c_i\) decides to throw a party of a different type.
Every night, each cow will attempt to go to a party. If a cow is not hosting a
party, they will check their best friend's barn, and if there is no party there,
will follow their best friend to wherever they are going (who might also follow
their best friend and so on). It is possible that a cow might never find a party
and will then give up for the night.
Compute for each night, the number of cows that end up at a party of type \(C\),
\(O\), and \(W\) respectively.
Problem credits: Benjamin Qi
SCORING
- Input 2: \(N, M\leq 100\)
- Inputs 3-4: \(N, M\leq 4000\)
- Inputs 5-9: \(\{a_i\}\) is a permutation of \(\{1,\dots, N\}\)
- Inputs 10-21: No additional constraints
Problem credits: Benjamin Qi
The first line contains \(N\), the number of cows.
The second line contains \(a_1,\dots, a_N\), where \(a_i\) is cow \(i\)'s best friend.
The third line contains \(M\), the number of nights.
The next \(M\) lines each contain an integer \(c_i\) (\(1\le c_i\le N\)) and a
character \(v_i\), representing the cow that is throwing the party and the party
type respectively.
Output \(M\) lines, where the \(i\)th consists of \(3\) space-separated integers, the
number of cows going to parties of type \(C\), \(O\), and \(W\) on the \(i\)th night,
respectively.
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
평가 및 의견
COW Traversals
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
COW Traversals