레이팅 미적용농부 존에게는 \(1\dots N\)으로 라벨이 붙은 \(N\) (\(2\le N\le 10^5\))마리의 소가 있으며, 소들 사이의 연결 관계는 트리로 표현된다. 안타깝게도 소들 사이에 병이 퍼지고 있다.
처음에 일부 소들이 감염된 상태로 시작한다. 매일 밤, 감염된 소는 자신의 이웃들에게 병을 퍼뜨린다. 한 번 감염된 소는 계속 감염된 상태로 남는다. 며칠 밤이 지난 후, 농부 존은 문제가 있음을 깨닫고 소들을 검사하여 누가 병에 걸렸는지 알아냈다.
밤의 수에 대한 \(Q\) (\(1\le Q\le 20\))개의 서로 다른 값이 주어지며, 각 값은 \([0,N]\) 범위의 정수이다. 각 밤의 수에 대해, 처음에 병을 가지고 시작했을 수 있는 소의 최소 마릿수를 구하거나, 그 밤의 수가 주어진 정보와 모순됨을 판별하라.
문제 제공: Suhas Nagar, Brandon Wang
채점 방식
- 입력 4-5: \(N \le 10\)
- 입력 6-8: 모든 소가 감염되어 있다.
- 입력 9-11: \(N \le 400\)
- 입력 12-23: 추가 제약 조건 없음.
문제 제공: Suhas Nagar, Brandon Wang
첫째 줄에 \(N\)이 주어진다.
다음 줄에 길이 \(N\)의 비트 문자열이 주어진다. \(i\)번째 비트는 \(i\)번째 소가 감염되었으면 1, 아니면 0이다. 적어도 한 마리의 소는 감염되어 있다.
다음 \(N-1\)개의 줄에 트리의 간선이 주어진다.
그다음 \(Q\)가 주어지고, 이어서 밤의 수에 대한 \(Q\)개의 값이 주어진다.
\(Q\)개의 줄에 걸쳐 각 밤의 수에 대한 답을 출력하고, 불가능하면 \(-1\)을 출력한다.
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