Anna is a resident of the IOI islands and has invited Bruno to visit. The N islands in the IOI islands are numbered from 1 to N. There are N - 1 bridges between the IOI islands which are numbered from 0 to N - 2. The ith bridge connects islands Ai and Bi. It is possible to move from each island to all other islands using only the bridges. Anna lives at island T, but Bruno does not know the number of the island at which Anna lives.
To help Bruno, Anna is able to place one flag at each of the N islands. Each flag can have one integer written on it. Anna does not know which island Bruno will arrive at.
Bruno has arrived on island S by boat. When Bruno arrives, he is given the following information:
- The island number of the island he arrived at, S, and the integer written on the flag at S.
- The island numbers of the islands that S has bridges to, along with the integers written on the flags at those islands.
Bruno must move from S to T on the path that uses the smallest possible number of bridges. Given only the information above, Bruno must either determine that he is at island T, or determine the correct island to proceed next to in order to reach T using the smallest number of bridges.
Anna, being a resident, knows how the IOI islands and the bridges between them are laid out. She must determine the integers to write on the flags at each island. Bruno must be able to navigate to T from any island he arrives at, using only the information given to him and still crossing the smallest possible number of bridges.
Implementation Details
You should write two files, Anna.cpp and Bruno.cpp.
The first file Anna.cpp must include Annalib.h and implement the following functions:
You must call the following function to set the integers to be written on the flags:
-
void Flag(int I, int V)
- Parameter
I is the island number where this flag is to be placed.
- Parameter
V is the number to be written on the flag.
The calls to Flag must satisfy the following constraints:
I must be greater than or equal to 1 and less than or equal to N. If this constraint is not satisfied, the message "Wrong Answer [1]" will be shown.Flag must not be called more than once with the same value of I. If this constraint is not satisfied, the message "Wrong Answer [2]" will be shown.V must be greater than or equal to 0 and less than or equal to N. If this constraint is not satisfied, the message "Wrong Answer [3]" will be shown.Flag must be called exactly N times. If this constraint is not satisfied, the message "Wrong Answer [4]" will be shown.
If any call to Flag is determined to be incorrect, the program will terminate.
The second file Bruno.cpp must include Brunolib.h and implement the following functions:
After determining the correct island Bruno should move to or that the island Bruno is on is Anna's home island, you must call the following function to indicate the answer:
-
void Answer(int X)
Parameter X is your answer. If the island Bruno has arrived at, S, is Anna's home island, T, X must be T. Otherwise, X must be the next island Bruno should move to from S.
The call the Answer must satisfy the following constraints:
X must either be S or one of the L elements of P. If this constraint is not satisfied, the message "Wrong Answer [5]" will be shown.- Answer must not be called more than once. If this constraint is not satisfied, the message "Wrong Answer [6]" will be shown.
- Answer must be called. If this constraint is not satisfied, the message "Wrong Answer [7]" will be shown.
- If island
S is Anna's home island, and X is not T, the message "Wrong Answer [8]" will be shown.
- If island
S is not Anna's home island, and X is not the correct next island Bruno should move to, the message "Wrong Answer [9]" will be shown.
After Bruno has been called, the program will determine the correctness of your answer and terminate.
You are free to declare global variables or other functions to aid in your implementation. However, in order to avoid interference when compiling with the sample grader, you should declare all global variables static. It is not possible to share data between the two programs as they are graded separately during evaluation. You are not allowed to read or print from/to standard input/output within your program.
Compiling with the Sample Grader
A sample grader is provided to aid you in writing your program. To compile the grader, run the following command:
g++ std=c++11 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
Sample Grader Input
The sample grader reads from standard input.
- On the first line, there are 4 integers, N, S, T and K. This means there are N islands in the IOI islands, Bruno arrives at island S and Anna lives on island T. In addition, the subtask number is K.
- On the (i + 1)th line of the next N - 1 lines (0 ≤ i ≤ N - 2), there are two integers, Ai and Bi. This means bridge i connects islands Ai and Bi.
- On the next line, there is one integer Y. This is the correct answer. If
Answer was called with X = Y, your answer will be judged as correct and wrong otherwise.
Sample Grader Output
The sample grader prints to standard output.
- If your answer was correct, the sample grader will print the largest value of
V in any call to Flag. For example, if the largest value of V used in any call to Flag is 2, the sample grader will print "Accepted : V_max = 2".
- If your answer was wrong, the sample grader will print the error message, for example "Wrong Answer [1]".
Constraints
All test cases satisfy the following constraints.
- 2 ≤ N ≤ 100 000.
- 1 ≤ S ≤ N.
- 1 ≤ T ≤ N.
- 1 ≤ Ai ≤ N (0 ≤ i ≤ N - 2).
- 1 ≤ Bi ≤ N (0 ≤ i ≤ N - 2).
- 1 ≤ K ≤ 4.
- It is possible to move to all other IOI islands from any IOI island using only the bridges given.
Subtasks
Subtask 1 (10 points):
Subtask 2 (15 points):
- K = 2 is satisfied.
- Flag must be called with parameter
V greater than or equal to 0 and less than or equal to 2.
Subtask 3 (20 points):
- K = 3 is satisfied.
- Flag must be called with parameter
V either 0 or 1.
- There are no IOI islands which are connected to only two other IOI islands directly by bridges.
- S ≠ T is satisfied.
Subtask 4 (55 points):
- K = 4 is satisfied.
- Flag must be called with parameter
V either 0 or 1.
Sample Input 1
5 3 2 1
1 3
3 2
3 4
4 5
2
Sample Exchange 1
| Anna | Bruno |
|---|
Anna(...) | |
Flag(1, 1) | |
Flag(2, 1) | |
Flag(3, 0) | |
Flag(4, 0) | |
Flag(5, 1) | |
| Bruno(...) |
| Answer(2) |
The sample calls to Flag shown here do not necessarily have any meaning. The parameters supplied to Anna and Bruno are shown as follows:
| Parameter | Anna(...) |
|---|
K | 1 |
N | 5 |
T | 2 |
A | {1, 3, 3, 4} |
B | {3, 2, 4, 5} |
| Parameter | Bruno(...) |
|---|
K | 1 |
S | 3 |
F | 0 |
P | {2, 1, 4} |
Q | {1, 1, 0} |