시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 94 | 22 | 19 | 32.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 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)
N
represents N, the number of islands.Your program can call the following functions.
int Query(int u, int v, int w)
void Bridge(int u, int v)
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) |
번호 | 배점 | 제한 |
---|---|---|
1 | 7 | N ≤ 7. |
2 | 10 | N ≤ 50. |
3 | 12 | N ≤ 300. |
4 | 71 | No additional constraints. |
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)