2024-sp_Island_Hopping — JOI JOI_spring
Task type: interactive | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: graph reconstruction, graph theory, interactive, tree

![](_page_0_Picture_0.jpeg)

# Island Hopping

There are *N* islands in JOI Kingdom, numbered from 1 to *N*. There are *N* − 1 sea routes in JOI Kingdom, numbered from 1 to *N* − 1. The sea route *j* (1 ≤ *j* ≤ *N* − 1) connects island *A<sub>j</sub>* and island *B<sub>j</sub>* bi-directionally. It is possible to travel from any island to any other island by using some sea routes.

Aoi is planning a trip in JOI Kingdom. However, she doesn't know about sea routes in JOI Kingdom. She is going to ask questions with Bitaro, a citizen in JOI Kingdom, in the following way:

1.  Aoi tells Bitaro an integer *v*, where 1 ≤ *v* ≤ *N*, and an integer *k*, where 1 ≤ *k* ≤ *N* − 1.
2.  Bitaro tells Aoi the number on the island which is the *k*-th closest from island *v* among the *N* − 1 islands except for island *v*. To be specific, he tells her an integer *i* that dist(*v*, *i*) × *N* + *i* (1 ≤ *i* ≤ *N*, *i* ≠ *v*) is the *k*-th smallest, where dist(*v*, *i*) is the minimum number of sea routes to move from island *v* to island *i*.

Aoi wants to know all sea routes in JOI Kingdom by asking questions to Bitaro. Since Aoi does not want to spend too much time, she can ask at most *L* questions to Bitaro.

Write a program which, given the number of islands in JOI Kingdom and the limit on number of questions to Bitaro, implements Aoi's strategy to find all sea routes.

![](_page_1_Picture_0.jpeg)

## Implementation Details

You need to submit one file.

The file is `island.cpp`. It should implement the following function. The program should include `island.h` using the preprocessing directive `#include`.

*   **`void solve(int N, int L)`**

    This function is called only once for each test case.
    *   The parameter `N` is the number of islands *N*.
    *   The parameter `L` is the limit on the number of questions *L*.

In `island.cpp`, you can call the following function.

*   **`int query(int v, int k)`**

    Using this function, Aoi asks a question to Bitaro.
    *   The parameter `v` must be between 1 and *N*. If not, your program is judged as `Wrong Answer [1]`.
    *   The parameter `k` must be between 1 and *N* − 1. If not, your program is judged as `Wrong Answer [2]`.
    *   The return value is the number on the island which is the *k*-th closest from island *v* among the *N* − 1 islands except for island *v*. See the problem statement for a more detailed definition.
    *   You must not call the function `query` more than *L* times. If it is called more than *L* times, your program is judged as `Wrong Answer [3]`.

*   **`void answer(int x, int y)`**

    Your program answers a sea route in JOI Kingdom by calling this function.
    *   The parameters `x` and `y` are the numbers of two islands connected by a sea route.
    *   The parameters `x` and `y` must be between 1 and *N*. If not, your program is judged as `Wrong Answer [4]`.
    *   There must exist a sea route which connects islands `x` and `y`. In other words, there must exist an integer *j* (1 ≤ *j* ≤ *N* − 1) such that `x` = *A<sub>j</sub>* and `y` = *B<sub>j</sub>*, or `x` = *B<sub>j</sub>* and `y` = *A<sub>j</sub>*. If not, your program is judged as `Wrong Answer [5]`.
    *   The program must not answer the information of the same sea route twice or more. If this condition is not met, your program is judged as `Wrong Answer [6]`.
    *   The function `answer` must be called exactly *N* − 1 times. If the number of calls to the function `answer` is not *N* − 1 when the execution of the function `solve` ends, your program is judged as `Wrong Answer [7]`.

![](_page_2_Picture_0.jpeg)

## Important Notices

*   Your program can implement other functions for internal use or use global variables.
*   Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

## Compilation and Test Run

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`, `island.cpp`, and `island.h` in the same directory, and run the following command to compile your programs. Instead, you may run `compile.sh` contained in the archive file.

```bash
g++ -std=gnu++20 -O2 -o grader grader.cpp island.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:

```
N L
A1 B1
A2 B2
...
AN-1 BN-1
```

## Output for the Sample Grader

The sample grader outputs the following information to the standard output (quotes for clarity):

*   If your program is judged as correct, it reports the number of calls to `query` as `"Accepted: 2024"`.

![](_page_3_Picture_0.jpeg)

*   If your program is judged as any type of Wrong Answer, the sample grader writes its type as `"Wrong Answer [4]"`.

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

## Notices for Grading

The actual grader is not adaptive for all test cases. It means that the grader has a pre-determined answer for each test case.

## Constraints

All the input data satisfy the following conditions:

*   3 ≤ *N* ≤ 300.
*   1 ≤ *A<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *N* − 1).
*   1 ≤ *B<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *N* − 1).
*   *A<sub>j</sub>* ≠ *B<sub>j</sub>* (1 ≤ *j* ≤ *N* − 1).
*   It is possible to travel from any island to any other island by using some sea routes.
*   Given values are all integers.

## Subtasks

1.  (2 points) *N* = 3, *L* = 9.
2.  (4 points) *L* = *N*<sup>2</sup>. Each island has at most 2 connecting sea routes.
3.  (7 points) *L* = 2\*N. Each island has at most 2 connecting sea routes.
4.  (9 points) *L* = *N*<sup>2</sup>. Island 1 has 3 connecting sea routes, and each of the other islands have at most 2 connecting sea routes.
5.  (13 points) *L* = 3\*N. Island 1 has 3 connecting sea routes, and each of the other islands have at most 2 connecting sea routes.
6.  (15 points) *L* = *N*<sup>2</sup>.
7.  (22 points) *L* = 3\*N.
8.  (28 points) *L* = 2\*N.

![](_page_4_Picture_0.jpeg)

## Sample Communication

Here is a sample input for the sample grader and corresponding function calls.

| Sample Input 1 | Sample Function Calls | Calls        | Return Values |
| :------------- | :-------------------- | :----------- | :------------ |
| 4 16           | `solve(4, 16)`       |              |               |
| 1 2            |                       | `query(2, 1)`  | 1             |
| 2 4            |                       | `query(3, 1)`  | 4             |
| 4 3            |                       | `answer(2, 4)` |               |
|                |                       | `query(2, 2)`  | 4             |
|                |                       | `answer(2, 1)` |               |
|                |                       | `query(3, 2)`  | 2             |
|                |                       | `query(2, 1)`  | 1             |
|                |                       | `answer(3, 4)` |               |

The minimum number of sea routes to move from island 2 to islands 1, 3, 4 are 1, 2, 1, respectively. For example, to move from island 2 to island 3, we can use sea route 2 and then sea route 3.

Sorting the islands *i* (*i* ≠ 2) in increasing order of dist(2, *i*) × *N* + *i*, the result is island 1, island 4, island 3, in this order. Therefore, the return value of `query(2, 1)` is 1, and the return value of `query(2, 2)` is 4.

Sample Input 1 satisfies the constraints of Subtasks 2 and 6. Among the files which can be obtained from the contest webpage, `sample-01-in.txt` corresponds to Sample Input 1.

![](_page_5_Picture_0.jpeg)

| Sample Input 2 | Sample Function Calls | Calls        | Return Values |
| :------------- | :-------------------- | :----------- | :------------ |
| 5 25           | `solve(5, 25)`       |              |               |
| 5 2            |                       | `query(1, 3)`  | 5             |
| 3 1            |                       | `query(1, 4)`  | 2             |
| 1 4            |                       | `answer(3, 1)` |               |
| 1 5            |                       | `query(2, 4)`  | 4             |
|                |                       | `query(3, 1)`  | 1             |
|                |                       | `query(3, 2)`  | 4             |
|                |                       | `answer(1, 5)` |               |
|                |                       | `answer(4, 1)` |               |
|                |                       | `answer(2, 5)` |               |

The minimum number of sea routes to move from island 1 to islands 2, 3, 4, 5 are 2, 1, 1, 1, respectively. For example, to move from island 1 to island 2, we can use sea route 4 and then sea route 1.

Sorting the islands *i* (*i* ≠ 1) in increasing order of dist(1, *i*) × *N* + *i*, the result is island 3, island 4, island 5, and island 2, in this order. Therefore, the return value of `query(1, 3)` is 5, and the return value of `query(1, 4)` is 2.

Sample Input 2 satisfies the constraints of Subtasks 4 and 6. Among the files which can be obtained from the contest webpage, `sample-02-in.txt` corresponds to Sample Input 2.

Both `sample-01-in.txt` and `sample-02-in.txt` can be used as inputs for the sample grader.

Starter code:
grader.cpp: #include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <random>
#include <utility>
#include <vector>

#include "island.h"

namespace {

const int invalid_v_range = 1;
const int invalid_k_range = 2;
const int query_limit_exceeded = 3;
const int invalid_xy_range = 4;
const int no_edge = 5;
const int answer_twice = 6;
const int invalid_answer_times = 7;

int N, L, ok;
std::vector<int> A, B, answered;
std::vector<std::vector<int>> g, dist, que;
std::vector<std::pair<int, int>> p;

int query_count = 0;
int answer_count = 0;

void wronganswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

void dfs(int now, int pre, std::vector<std::vector<int>> &g,
         std::vector<int> &dist) {
  for (int nxt : g[now]) {
    if (nxt == pre) {
      continue;
    }
    dist[nxt] = dist[now] + 1;
    dfs(nxt, now, g, dist);
  }
}

}  // namespace

int query(int v, int k) {
  if (v < 1 || N < v) {
    wronganswer(invalid_v_range);
  }
  if (k < 1 || N - 1 < k) {
    wronganswer(invalid_k_range);
  }

  query_count++;
  if (query_count > L) {
    wronganswer(query_limit_exceeded);
  }

  return que[v - 1][k] + 1;
}

void answer(int x, int y) {
  if (x < 1 || N < x || y < 1 || N < y) {
    wronganswer(invalid_xy_range);
  }
  if (x > y) {
    std::swap(x, y);
  }

  answer_count++;
  if (answer_count > N - 1) {
    wronganswer(invalid_answer_times);
  }

  ok = -1;
  for (int i = 0; i < N - 1; i++) {
    if (A[i] == x && B[i] == y) {
      if (answered[i] != 0) {
        wronganswer(answer_twice);
      }
      ok = i;
    }
  }

  if (ok == -1) {
    wronganswer(no_edge);
  }

  answered[ok] = 1;
}

int main(int argc, char **argv) {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  if (scanf("%d", &L) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }

  A.resize(N - 1);
  B.resize(N - 1);
  answered.resize(N - 1, 0);
  g.resize(N);
  dist.resize(N, std::vector<int>(N));
  que.resize(N);

  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &A[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
    if (scanf("%d", &B[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (A[i] >= B[i]) {
      std::swap(A[i], B[i]);
    }
    g[A[i] - 1].emplace_back(B[i] - 1);
    g[B[i] - 1].emplace_back(A[i] - 1);
  }

  for (int i = 0; i < N; i++) {
    dist[i][i] = 0;
    dfs(i, -1, g, dist[i]);

    p.clear();
    for (int j = 0; j < N; j++) {
      p.emplace_back(dist[i][j], j);
    }
    std::sort(p.begin(), p.end());

    for (int j = 0; j < N; j++) {
      que[i].emplace_back(p[j].second);
    }
  }

  solve(N, L);
  if (answer_count != N - 1) {
    wronganswer(invalid_answer_times);
  }
  printf("Accepted: %d\n", query_count);
  return 0;
}
island.cpp: #include "island.h"

void solve(int N, int L) {
  int variable_example = query(1, 1);
  for (int i = 2; i <= N; i++) {
    answer(1, i);
  }
}
island.h: void solve(int N, int L);

int query(int v, int k);

void answer(int x, int y);