Cowntact Tracing
루비 V의견: 0
Farmer John has \(N\) (\(2\le N\le 10^5\)) cows labeled \(1\dots N\), where the
connections between cows are described by a tree. Unfortunately, there is a
sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads
the sickness to their neighbors. Once a cow is infected, she stays infected.
After some amount of nights, Farmer John realizes that there is an issue so he
tests his cows to determine who has the sickness.
You are given \(Q\) (\(1\le Q\le 20\)) different values for the number of nights,
each an integer in the range \([0,N]\). For each number of nights, determine the
minimum number of cows that could have started with the illness, or that the
number of nights is inconsistent with the given information.
Problem credits: Suhas Nagar and Brandon Wang
SCORING
- Inputs 4-5: \(N \le 10\)
- Inputs 6-8: All cows are infected.
- Inputs 9-11: \(N \le 400\)
- Inputs 12-23: No additional restrictions.
Problem credits: Suhas Nagar and Brandon Wang
The first line contains \(N\).
The next line contains a bit string of length \(N\), where the \(i\)th bit is 1 if
the \(i\)th cow is infected and 0 otherwise. At least one cow is infected.
The next \(N-1\) lines contain the edges of the tree.
Then \(Q\), followed by the \(Q\) values for the number of nights.
\(Q\) lines, the answers for each number of nights, or \(-1\) if impossible.
5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
01
1
1
1
2
5For the first four queries, one possibility is that just cow 3 started with the
illness. For the fifth query (1 night), one possibility is that cows 2 and 4
started with the illness. For the sixth query (0 nights), one possibility is
that all five cows started with the illness.
10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
1010
3
2
1
1
1
1
1
1
1
1For the first query (0 nights), one possibility is that all ten cows started
with the illness. For the second query (1 night), one possibility is that cows
2, 7, and 9 started with the illness. For the third query (2 nights), one
possibility is that cows 2 and 9 started with the illness. For the fourth to
eleventh queries, one possibility is that just cow 7 started with the illness.
5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
53
1
1
-1
-1
-1For the first query (0 nights), one possibility is that cows 1, 2, and 3 started
with the illness. For the second query (1 night), one possibility is that just
cow 2 started with the illness. For the third query (2 nights), one possibility
is that just cow 1 started with the illness. For the fourth through sixth
queries, there is no consistent possibility.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Platinum
평가 및 의견
Cowntact Tracing
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cowntact Tracing