시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
A D-Balanced Tree (D being a positive integer) is a tree that satisfies the following conditions:
You are given a tree that may not have the colour of every node decided yet. You have to choose the colour of all remaining nodes in order to minimize the value of D. However, there may be no valid positive integer D such that the tree is D-Balanced (see example).
Full score will be given only if you found a valid coloring that leads to your answer.
On the first line of the standard input there is a positive integer T representing the number of test cases that will follow. Each test case describes a tree and consists of :
Depending on ci, the color of a node can be :
The output should contain the answer for each test case on different lines.
Each answer is structured as follows :
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | N ≤ 17, T ≤ 500 |
2 | 13 | sum of N ≤ 100 000, ci ∈ {0, 1} |
3 | 26 | sum of N ≤ 100 000, all trees in input are paths |
4 | 45 | sum of N ≤ 100 000 |
5 | 6 | no additional restriction |
3 3 1 2 2 3 0 0 -1 4 1 2 2 3 2 4 0 1 0 0 6 1 2 2 3 2 4 4 5 4 6 1 0 0 -1 1 0
1 0 0 0 -1 2 1 0 0 1 1 0
Contest > infO(1) Cup > infO(1) Cup 2018 International Round 4번