시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB94221932.203%

문제

There are N islands where beavers live, numbered from 0 through N − 1. These islands are connected by N − 1 bidirectional bridges. It is possible to travel between any islands using some bridges. For each island, there are at most 18 bridges directly connected to it. Each island is inhabited by a beaver.

Sometimes, some beavers gather at an island to hold a meeting. When exactly three beavers meet, they gather at the following island:

The island which minimizes the total number of bridges the three beavers travel through when gathering (such island uniquely exists).

Note that this island may coincide with an island where one of the three beavers lives.

You are interested in how N islands are connected by bridges. You cannot go and check the islands directly, so you are going to issue some instructions to the beavers. An instruction is as follows:

  • You specify three islands u, v and w (0 ≤ u ≤ N − 1, 0 ≤ v ≤ N − 1, 0 ≤ w ≤ N − 1, u , v, u , w, v , w), and let the beavers living in the islands u, v and w hold a meeting.
  • Then, you can see the island where the three beavers gather.

You want to determine how the islands are connected with few instructions.

Write a program which, given the number of islands, communicating with beavers, determine how the islands are connected.

구현

You need to submit one file.

The name of the file is meetings.cpp. It should implement the following function. The program should include meetings.h.

  • void Solve(int N)
    This function is called exactly once for each test case.
    • The parameter N represents N, the number of islands.

Your program can call the following functions.

  • int Query(int u, int v, int w)
    This function returns, for the indices of three islands you specify, the index of the island where the beavers living there gather for a meeting.
    • You specify the indices u, v and w of the three islands via parameters u, v and w, respectively. These must satisfy 0 ≤ u ≤ N − 1, 0 ≤ v ≤ N − 1, 0 ≤ w ≤ N − 1, u , v, u , w and v , w. Otherwise, your program is considered as Wrong Answer [1].
    • The function Query must not be called more than 100 000 times. Otherwise, your program is considered as Wrong Answer [2].
  • void Bridge(int u, int v)
    Using this function, you answer how the islands are connected by bridges.
    • The parameters u and v represent that the islands u and v are directly connected by a bridge.
    • If 0 ≤ u < v ≤ N − 1 does not hold, your program is considered as Wrong Answer [3].
    • If the islands u and v are not directly connected by a bridge, your program is considered as Wrong Answer [4].
    • If the function Bridge is called with the same parameters u and v multiple times, your program is considered as Wrong Answer [5].
    • Since there are N − 1 bridges, the function Bridge must be called exactly N − 1 times. If the number of calls to the function Bridge is not N − 1 at the end of the execution of the function Solve, your program is considered as Wrong Answer [6].

제한

  • 3 ≤ N ≤ 2 000.
  • 0 ≤ Ai < Bi ≤ N − 1 (0 ≤ i ≤ N − 2).
  • It is possible to travel between any islands using some bridges.
  • For each island, there are at most 18 bridges directly connected to it.

Ai and Bi (0 ≤ i ≤ N − 2) represent that the islands Ai and Bi are directly connected by a bridge.

예시

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

Sample Input 1 Sample Calls
Call Call Return
5
0 1
0 2
1 3
1 4
Solve(5)    
  Query(0, 1, 2) 0
  Query(0, 3, 4) 1
  Bridge(1, 3) (none)
  Bridge(0, 2) (none)
  Bridge(1, 4) (none)
  Bridge(0, 1) (none)

서브태스크

번호배점제한
17

N ≤ 7.

210

N ≤ 50.

312

N ≤ 300.

471

No additional constraints.

점수

  • For Subtasks 1, 2 and 3, if your program is correct for all test cases in a subtask, you are given the full score.
  • For Subtask 4, if your program is correct for all test cases, your score will be the following, where X is the maximum number of calls to the function Query for a test case.
    • 49 points if 40 000 < X ≤ 100 000, and
    • 71 points if X ≤ 40 000.

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.