QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100 Interactive

# 5029. 在路上

统计

题目背景

dottle bot。

题目描述

这是一道交互题,仅支持 C++,C++11,C++14,C++17 提交。

有一棵未知的树,保证树的大小为奇数,你需要找到这棵树重心的编号。

你可以进行询问,每次询问你可以询问三个点 $(x,y,z)$,若不存在一条简单路径同时经过三个点,则交互器会返回 $0$,否则若存在,那么交互器会返回三个点在路径上相对顺序中间的一个点。

令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数,你也可以理解为:

  • 若 $dis(x,y)+dis(x,z)=dis(y,z)$,则交互器会返回 $x$。
  • 否则若 $dis(y,x)+dis(y,z)=dis(x,z)$,交互器会返回 $y$。
  • 否则若 $dis(z,x)+dis(z,y)=dis(x,y)$,交互器会返回 $z$。
  • 否则交互器会返回 $0$。

在最终的测试中,每个测试点会包含 $T$ 组测试数据,和一个常数 $M$,表示你在所有测试数据中询问次数总和的上限,具体细则见 输入格式 以及 数据范围。

实现细节

你需要引用 path.h 头文件。

你需要实现下面的函数:

int centroid(int id,int N,int M);
  • 其中 $id$ 为当前子任务的编号,$N$ 为当前询问树的大小,$M$ 为当前测试点剩余的询问次数,函数的返回值为当前树的重心编号。
  • 具体的,在第一次调用时 $M$ 为当前测试点的询问次数上限,每次调用结束之后 $M$ 会减去当前测试点使用的询问次数。

你可以调用下面的函数:

int ask(int x,int y,int z);
  • 表示你进行了一次询问,交互器会返回当前询问的答案,特别的,若询问次数已经超过了上限,交互器会返回 $−1$。
  • 注意同一个测试点中 centroid 函数可能会被多次调用,请注意数组清空等情况。

下发文件中有样例交互库,该交互库的实现与评测时的交互库几乎一致,如果对交互方式有不理解可以参照交互库的代码理解。

评测方式

样例评测库将读入如下格式的输入数据:

第一行三个整数 $id,T,M$,表示当前的子任务编号以及测试数据的数量,以及询问次数的上界。

对于每一组测试数据,第一行一个正整数 $n$,表示当前测试数据中树的大小。

之后一行 $n−1$ 个正整数,第 $i$ 个数表示 $i+1$ 在以 $1$ 为根意义下的父亲节点。

数据的答案将在交互库内部计算。

数据范围

子任务编号 子任务分数 $t$ $n$ $M$ 特殊性质
$1$ $2$ $=100$ $=3$ $=100$
$2$ $8$ $=10$ $=999$ $=10^7$
$3$ $12$ $=100$ A
$4$ $17$
$5$ $18$ $=49\,999$ $=2.5 \times 10^7$ A
$6$ $12$ $=9\,999$ $=4\times 10^7$
$7$ $19$ $=50$ $=29\,999$
$8$ $12$ $=100$ $=5\times 10^7$

特殊性质 A:保证树的形态为一条链,即每个点的度数均不超过 $2$。

保证每个 Subtask 里的测试数据数量均不超过 $20$。

请仔细阅读每一档子任务及其限制。

下发文件

下发文件中有一个样例交互库,提供的交互头文件,一份示例代码,以及一个满足子任务 $4$ 性质的样例,选手也可以按照题目的输入格式构造其他样例。

保证下发的交互库和最终使用的交互库除反作弊之外没有区别,你可以使用这个交互库输出调试信息。

保证最终交互库的时间使用不超过 2s,空间使用不超过 64MB。