#3031. 「JOISC 2019 Day1」聚会

内存限制:268 MiB 时间限制:2000 ms 题目类型:交互
上传者: EntropyIncreaser

题目描述

题目译自 JOISC 2019 Day1 T2「ビーバーの会合 / Meetings

N 座住有海狸的岛屿,编号从 0 N - 1 。这些岛由 N - 1 条双向桥梁连接,使得两两互相可达。保证每个岛屿至多连出 \mathbf{18} 座桥。每个岛住有一只海狸。

有时,一些海狸会赶往同一个岛屿进行聚会。当三只海狸进行聚会的时候,它们会按照这一规则选择聚会的岛屿:

  • 找到一个岛屿,使得三只海狸到达这个岛屿的距离之和是最小的,可以证明这样的岛屿是唯一的。 这个岛屿可以是其中某一个海狸的家。

你的任务是找出这 N 座岛屿的连接方式。为了获取信息,你可以问海狸这样一个问题:

  • 给出三个不同的岛屿 u, v, w
  • 询问这三座岛屿上的海狸会赶往聚会的岛屿。

实现细节

你的程序在开头需包含头文件 meetings.h,并实现函数:

void Solve(int N)

该函数每个测试点会被调用一次,参数 N 表示岛屿的数量 N

你的程序可以调用函数:

int Query(int u, int v, int w)
  • 表示询问来自岛屿 u,v,w 的海狸聚会的位置岛屿。
  • 参数需要满足 0\le u,v,w \le N - 1 u\neq v, u\neq w, v\neq w ,否则会被判定为 Wrong Answer [1]
  • 你的程序运行时调用该函数的次数不能超过 10^5 次,否则会被判定为 Wrong Answer [2]
void Bridge(int u, int v)
  • 表示你确认了 u,v 间有一座桥。
  • 参数需满足 0\le u < v\le N - 1 ,否则会被判定为 Wrong Answer [3]
  • 如果事实上 u,v 间不存在桥,会被判定为 Wrong Answer [4]
  • 如果一组 u,v 被调用了多次,会被判定为 Wrong Answer [5]
  • 运行时此函数应被恰被调用 N - 1 次,否则会被判定为 Wrong Answer [6]

注意事项

  • 你可以定义一些其他的函数和全局变量。
  • 你的程序中不允许进行标准输入输出,但可以通过错误流进行输出。

编译与运行方法

在下发文件中有一个样例评测程序 grader.cpp,假设你的文件是 meetings.cpp,将 grader.cppmeetings.hmeetings.cpp 放置在同一个目录下,运行:

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

会生成一个可执行文件 grader,他通过标准输入输出流进行输入和输出。

输入格式

指样例评测程序输入格式。

第一行读入一个正整数 N

接下来 N - 1 行,每行两个整数 A,B ,表示岛屿 A,B 间有一座桥。

输出格式

指样例评测程序输出格式。

如果你的程序满足要求,输出 Accepted: 100

如果你的程序被判定为答案错误,输出形如 Wrong Answer [1]

样例

样例输入 1

5
0 1
0 2
1 3
1 4

样例交互

函数调用 返回值
Solve(5)
Query(0, 1, 2) 0
Query(0, 3, 4) 1
Bridge(1, 3)
Bridge(0, 2)
Bridge(1, 4)
Bridge(0, 1)

数据范围与提示

所有数据满足下列条件。 A_i, B_i 的含义参照「样例评测程序输入格式」一节。

  • 3 \le N \le 2000
  • 0 \le A_i, B_i \le N - 1
  • 保证岛屿之间两两互相可达。
  • 保证每个岛屿至多连出 18 座桥。

子任务

  • 子任务一( 7\% N\le 7
  • 子任务二( 10\% N\le 50
  • 子任务三( 12\% N\le 300
  • 子任务四( 71\% 没有附加限制。设 X 是你在本子任务测试点中进行最多的执行 Query() 的次数。
    • 4\times 10^4 <X \le 10^5 ,则获得 49\% 的分数。
    • X \le 4 \times 10^4 ,则获得 71\% 的分数。