시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 40 | 1 | 1 | 3.030% |
In Republic of JOI, there are $N$ airports numbered from $0$ to $N - 1$. There are $N - 1$ airline routes numbered from $0$ to $N - 2$. The airline route $i$ ($0 ≤ i ≤ N - 2$) connects the airport $U_i$ and the airport $V_i$ bidirectionally. It is possible to travel from any airport to any other airport by connecting several airline routes. For every airport, there are at most $3$ airline routes connecting it with another airport.
Benjamin is planning to take a trip in Republic of JOI. On the last day of the trip, he wants to arrive at the airport where the hot spring is located. The amusement park is located at the airport $x$, and the hot spring is located at the airport $y$. Since Benjamin does not know anything about the airline routes, he will communicate with Ali, a staff of the airplane company. Benjamin wants to know the minimum number of airline routes he has to take to travel from the airport where the amusement park is located to the airport where the hot spring is located. Ali knows information of the airplane routes. But Benjamin does not know which airline routes he has to take.
Write programs which implement the strategy of Ali, a staff of the airplane company, and the strategy of Benjamin, a traveler. Note that in Step 2, Benjamin can get the ID codes $X$, $Y$ of the airports where the amusement park and the hot spring are located. However, Benjamin cannot get the airport numbers $x$, $y$.
The first file is Ali.cpp
. It should implement Ali’s strategy. It should implement the following two functions. The program should include Ali.h
using the preprocessing directive #include
.
void Init(int N, std::vector<int> U, std::vector<int> V)
N
is the number of airports in Republic of JOI.U
, V
are arrays of length $N - 1$. This means U[i]
, V[i]
are the airports $U_i$, $V_i$ connected by the airline route $i$ ($0 ≤ i ≤ N - 2$).std::string SendA(std::string S)
SendB
(see below) is called.
S
is a string of length $20$. It is an e-mail message sent by Benjamin to Ali.SendA
should return a string. It is a latter written by Ali to Benjamin.0
or 1
. If this condition is not satisfied, your program is judged as Wrong Answer [6].For each function call to Init
, the following function should be called once for each airport. In total, it should be called $N$ times.
void SetID(int p, int value)
p
means Ali sets the ID code for the airport p
. Here $0 ≤ $p
$ ≤ N-1$ should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [1].value
is the ID code for the airport specified by Ali. Here $0 ≤ $value
$ ≤ 2N + 19$ should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [2].SetID
with same parameter p
more than once. If this condition is not satisfied, your program is judged as Wrong Answer [3].Init
terminates, the number of function calls to SetID
should be $N$. If this condition is not satisfied, your program is judged as Wrong Answer [4].When the function call to SetID
is judged as Wrong Answer, your program is terminated immediately.
The second file is Benjamin.cpp
. It should implement Benjamin’s strategy. It should implement the following two functions. The program should include Benjamin.h
using the preprocessing directive #include
.
std::string SendB(int N, int X, int Y)
Init
is called.
N
is the number of airports in Republic of JOI.X
is the ID code of the airport where the amusement park is located.Y
is the ID code of the airport where the hot spring is located.SendB
should return a string which is the e-mail message sent by Benjamin to Ali.0
or 1
. If this condition is not satisfied, your program is judged as Wrong Answer [8].SendA
is called.T
is a string whose length is between $1$ and $300\,000$, inclusive. It is the letter sent by Ali to Benjamin.A test case consists of $Q$ scenarios, numbered from $0$ to $Q - 1$. The following values are specified for each scenario. For the range of these values, see Constraints.
For each scenario, the functions Init
, SendB
, SendA
, Answer
are called. Your program should call appropriate functions with valid parameters, and return appropriate values. These functions are called in the following order.
Init
is called. The parameters are set for the scenario $k$ as specified in Implementation Details.SendB
is called. The parameters are set for the scenario $k$ as specified in Implementation Details.SendA
is called. The parameters are set for the scenario $k$ as specified in Implementation Details.Answer
is called. The parameters are set for the scenario $k$ as specified in Implementation Details.If your program is judged as Wrong Answer during these procedures, your program is terminated immediately, and your program is considered to fail the test case.
You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.
The sample grader is the file grader.cpp
. In order to test your program, put grader.cpp
, Ali.cpp
, Benjamin.cpp
, Ali.h
, Benjamin.h
in the same directory, and run the following command to compile your programs.
g++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp
When the compilation succeeds, the executable file grader
is generated.
Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.
Input for the Sample Grader
The sample grader reads the following data from the standard input. The input values should be all integers.
$\begin{align*} & Q \\ & \text{(Input for Scenario }0\text{)} \\ & \text{(Input for Scenario }1\text{)} \\ & \vdots \\ & \text{(Input for Scenario }Q-1\text{)} \\ \end{align*}$
The format of the input data for each scenario is as follows.
$\begin{align*} & N \, x \, y \\ & U_0 \, V_0 \\ & U_1 \, V_1 \\ & \vdots \\ & U_{N-2} \, V_{N-2} \\\end{align*}$
Output of the Sample Grader
If your program is judged as any one of Wrong Answer [1]-[8], the sample grader writes its type as “Wrong Answer [1]
” (quotes for clarity).
Otherwise, for each scenario, it writes the return value of the function Answer
and the maximum length of the strings sent by Ali to Benjamin. The sample grader does not check whether the return value of the function Answer
is correct or not.
Scenario 0: Your Answer = 3 Scenario 1: Your Answer = 1 Scenario 2: Your Answer = 4 Scenario 3: Your Answer = 1 Scenario 4: Your Answer = 5 Accepted: Maximum Length = 24
If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them. Moreover, if your program is not judged as Wrong Answer for the first scenario, the sample grader may output intermediate results as follows even if your program is judged as one of Wrong Answer [1]-[8] for a later scenario.
Scenario 0: Your Answer = 3 Scenario 1: Your Answer = 1 Scenario 2: Your Answer = 4 Wrong Answer [8]
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | $Q = 1$ |
2 | 85 | $Q \ge 2$. |
Grading for Subtask 1
If your program is judged as Wrong Answer in any of the scenarios for Subtask 1, your score for this subtask is $0$.
If your program answers all the test cases for Subtask 1 correctly, your score for this subtask is calculated as follows. Here, $L_1$ is the maximum length of the strings sent by Ali to Benjamin.
The value of $L_1$ | Score |
---|---|
$150\,001 ≤ L_1 ≤ 300\,000$ | $7$ points |
$20\,001 ≤ L_1 ≤ 150\,000$ | $11$ points |
$L_1 ≤ 20\,000$ | $15$ points |
Grading for Subtask 2
If your program is judged as Wrong Answer in any of the scenarios for Subtask 2, your score for this subtask is $0$.
If your program answers all the test cases for Subtask 2 correctly, your score for this subtask is calculated as follows. Here, $L_2$ is the maximum length of the strings sent by Ali to Benjamin. Note that if $1\,401 ≤ L_2$, your score for this subtask is $0$.
The value of $L_2$ | Score |
---|---|
$1\,401 ≤ L_2 ≤ 300\,000$ | $0$ points |
$71 ≤ L_2 ≤ 1\,400$ | $52 - 35 × \log_{10}{\left(\frac{L_2}{70}\right)}$ points |
$45 ≤ L_2 ≤ 70$ | $87 - 0.5 × L_2$ points |
$25 ≤ L_2 ≤ 44$ | $109 - L_2$ points |
$L2 ≤ 24$ | $85$ points |
1 4 0 2 0 1 1 2 2 3
Here is a sample input for the sample grader and corresponding function calls. In the following example, the ID codes of the airports $0$, $1$, $2$, $3$ set by Ali by calling the function Init
are $12$, $21$, $25$, $27$, respectively
Ali’s Call | Ali’s Return Value | Benjamin’s Call | Benjamin’s Return Value |
---|---|---|---|
Init(4,[0,1,2],[1,2,3]) |
|||
SetID(0,12) |
|||
SetID(1,21) |
|||
SetID(2,25) |
|||
SetID(3,27) |
|||
SendB(12,25) |
"00000111110000011111" |
||
SendA("00...11") |
"10" |
||
Answer("10") |
2 |
In this sample input, there are $N$ ($= 4$) airports and three airline routes.
Since we need to take at least two airline routes to travel from the airport $x$ ($= 0$) to the airport $y$ ($= 2$), the function Answer
should return 2
.
Note that the return value of the function SendB
is not the airport numbers $(x, y) = (0, 2)$. It returns the ID codes of the airports $(X, Y) = (12, 25)$.
2 10 0 9 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 15 12 8 0 1 0 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14
In this sample input, there are $Q = 2$ scenarios.
Answer
should return 9
.Answer
should return 6
.C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)