P10440 [JOIST 2024] Island Hopping / Island Hopping

**Due to some bugs, submitting with C++14 (GCC9) will cause a compilation error. Please use C++14 and other languages to submit.** **This problem is translated from [JOISC 2024](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html) Day4 T2 「[島巡り](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island.pdf) / [Island Hopping](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island-en.pdf)」**. Translation source: LOJ. **Do not include `island.h`**. You should add the following declarations at the top of your file: ``` int query(int, int); void answer(int, int); ``` The interactive files can be downloaded from the [JOI official website](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html).

**This is an interactive problem. The interactive library for this problem is non-adaptive.** The JOI country has $N$ islands, numbered from $1$ to $N$. There are $N-1$ routes, numbered from $1$ to $N-1$. Route $j\ (1\le j\le N-1)$ connects islands $A_j$ and $B_j$ bidirectionally. Starting from any island, you can reach any other island by traveling through some routes. Aoi is going to travel in the JOI country. However, she does not know the routes in the JOI country. She plans to ask Bitaro, who lives in the JOI country, questions in the following way: 1. Aoi tells Bitaro two integers $v$ and $k$, where $1\le v\le N,1\le k\le N-1$. 2. Bitaro tells her the index of the $k$-th closest island to $v$ among the other $N-1$ islands (excluding $v$). More precisely, he tells an integer $i$ such that $\text{dist}(v,i)\times N+i\ (1\le i\le N,i\neq v)$ is the $k$-th smallest, where $\text{dist}(v,i)$ is the minimum number of routes used to travel from island $v$ to island $i$. Aoi wants to find out all routes in the JOI country by asking questions. Since she does not want to spend too much time, she can ask Bitaro at most $L$ questions. Given the number of islands and the limit on the number of questions, write a program to simulate Aoi’s questioning strategy and determine all routes. ### Implementation Details You need to include the library `island.h` at the beginning of your program. You need to implement the following function. - `void solve(int N, int L)` This function is called exactly once for each test case. - The parameter `N` is the number of islands $N$. - The parameter `L` is the question limit $L$. In your program, you can call the following functions. - `int query(int v, int k)` Aoi uses this function to ask Bitaro a question. - The parameter `v` must be between $1$ and $N$. Otherwise, your program will be judged **Wrong Answer [1]**. - The parameter `k` must be between $1$ and $N-1$. Otherwise, your program will be judged **Wrong Answer [2]**. - The return value is the index of the $k$-th closest island to $v$ among the other $N-1$ islands excluding $v$. See the statement for the precise definition. - You must not call `query` more than $L$ times. Otherwise, your program will be judged **Wrong Answer [3]**. - `void answer(int x, int y)` Use this function to report one route in the JOI country. - The parameters `x` and `y` are two islands connected by a route. - The parameters `x` and `y` must be between $1$ and $N$. Otherwise, your program will be judged **Wrong Answer [4]**. - There must exist a route connecting islands `x` and `y`. In other words, there must exist an integer $j\ (1\le j\le N-1)$ such that $x=A_j,y=B_j$ or $x=B_j,y=A_j$. Otherwise, your program will be judged **Wrong Answer [5]**. - Your program must not report the same route two or more times. Otherwise, your program will be judged **Wrong Answer [6]**. - The function `answer` must be called exactly $N-1$ times. If, after `solve` finishes, the number of calls to this function is not $N-1$, your program will be judged **Wrong Answer [7]**. ### Notes - You may implement other functions for internal use, or use global variables. - Your program must not use standard input or standard output. Your program must not interact with other files in any way. However, your program may output debug information to standard error. - The interactor used in the judging is **not** adaptive. This means the answer for each test case is fixed in advance. ### Compilation and Execution You can download the sample interactor in the attachments to test your program. The attached files also contain a sample program. The sample interactor is the file `grader.cpp`. To test your program, put `grader.cpp`, `island.cpp`, and `island.h` in the same directory, and compile with the following command. You may also run `compile.sh` to compile your program. ```bash g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp ``` If compilation succeeds, an executable file `grader` will be generated. Note that the interactor used in the judging is different from the sample interactor. The sample interactor runs as a single process: it reads data from standard input and outputs results to standard output.

The input format of the sample grader is as follows. The first line contains two integers $N,L$. The next $N-1$ lines each contain two integers $A_j,B_j$.

The sample interactor will output the following information to standard output. - If your program is judged correct, it will report the number of calls to `query`, for example: `Accepted: 2024`. - If your program gets a certain Wrong Answer, the sample interactor will output its category, for example: `Wrong Answer [4]`. If your program satisfies multiple Wrong Answer categories, the sample interactor will report only one of them.

### Sample Interaction #### Sample Interaction $1$ The sample call process is shown in the table below. | Call | Call | Return value | | :------------: | :------------: | :----------: | | `solve(4, 16)` | | | | | `query(2, 1)` | $1$ | | | `query(3, 1)` | $4$ | | | `answer(2, 4)` | | | | `query(2, 2)` | $4$ | | | `answer(2, 1)` | | | | `query(3, 2)` | $2$ | | | `query(2, 1)` | $1$ | | | `answer(3, 4)` | | The minimum numbers of routes needed to travel from island $2$ to islands $1,3,4$ are $1,2,1$, respectively. For example, to travel from island $2$ to island $3$, we can use route $2$ and then route $3$. Sorting the islands by increasing $\text{dist}(2,i)\times N+i\ (i\neq 2)$ gives islands $1,4,3$. Therefore, the return value of `query(2, 1)` is $1$, and the return value of `query(2, 2)` is $4$. Sample $1$ satisfies the constraints of subtasks $2,6$. #### Sample Interaction $2$ The sample call process is shown in the table below. | Call | Call | Return value | | :------------: | :------------: | :----------: | | `solve(5, 25)` | | | | | `query(1, 3)` | $5$ | | | `query(1, 4)` | $2$ | | | `answer(3, 1)` | | | | `query(2, 4)` | $4$ | | | `query(3, 1)` | $1$ | | | `query(3, 2)` | $4$ | | | `answer(1, 5)` | | | | `answer(4, 1)` | | | | `answer(2, 5)` | | The minimum numbers of routes needed to travel from island $1$ to islands $2,3,4,5$ are $2,1,1,1$, respectively. For example, to travel from island $1$ to island $2$, we can use route $4$ and then route $1$. Sorting the islands by increasing $\text{dist}(1,i)\times N+i\ (i\neq 1)$ gives islands $3,4,5,2$. Therefore, the return value of `query(1, 3)` is $5$, and the return value of `query(1, 4)` is $2$. Sample $2$ satisfies the constraints of subtasks $4,6$. ### Constraints - $3\le N\le 300$ - $1\le A_j,B_j\le N\ (1\le j\le N-1)$ - $A_j\neq B_j\ (1\le j\le N-1)$ - You can travel through routes from any island to any other island. ### Subtasks | Subtask | Additional Constraints | Points | | :-----: | :--------------------------------------------------------------: | :----: | | $1$ | $N=3,L=9$ | $2$ | | $2$ | $L=N^2$, each island has at most two incident routes | $4$ | | $3$ | $L=2N$, each island has at most two incident routes | $7$ | | $4$ | $L=N^2$, island $1$ has three incident routes, each other island has at most two incident routes | $9$ | | $5$ | $L=3N$, island $1$ has three incident routes, each other island has at most two incident routes | $13$ | | $6$ | $L=N^2$ | $15$ | | $7$ | $L=3N$ | $22$ | | $8$ | $L=2N$ | $28$ | Translated by ChatGPT 5