QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100 Interactive

# 4919. Tree

Statistics

这是一道交互题。

有一棵$n$个节点的以$1$为根的树,你每次可以询问集合$T$,令$S_u$表示$u$子树内的点,$d(u,v)$表示$u$到$v$路径上的边数,交互库会返回:

$$V=\{x \mid \exists u\in T,x\in S_u\}\\D(T)=\sum_{i\in V,j\in V,i < j}d(i,j)$$

如果你返回的树和交互库同构,你将获得$40\%$的分数。

实现细节

你需要实现 std::vector<int> solve(int n); 其中$n$是节点数,返回的vector里面依次存储$2\sim n$的父亲节点,注意:不保证父亲节点编号小于子节点。

你可以使用 int query(std::vector<int> T); 来询问,意义如上。

正式评测时交互库仅添加防作弊措施,运行效率与下发文件相同。

本地测试时,交互库读入为:第一行一个整数$n$,第二行$n-1$个整数分别表示$2\sim n$的父亲。

例:

6
1 2 3 1 2

询问:

query({1})=31
query({3,5})=8
query({3})=1

返回:

{1,2,3,1,2}:  score=1.0
{1,2,3,2,1}:  score=0.4
{1,1,1,1,1}:  score=0.0

数据范围及子任务:

$n\le 1000$,下面 $T$ 表示你询问次数的上界。

  • A 特殊性质满足:这是一棵二叉树。
  • B 特殊性质满足:树随机,随机方式为:随机生成一个排列$p$,满足$p_1=1$,然后令$f_{p_i}$在$p_{1\sim i-1}$内随机生成。
$n$ $T$ 分数 特殊性质
$5$ $1\,000$ $5$ $ $
$100$ $10^5$ $5$
$5\,000$ $10$
$1\,000$ $2\times 10^5$ $10$
$10^5$ $10$ A
$10$ B
$10$ $ $
$5 \times 10^4$ $10$ A
$10$ B
$10$ $ $
$3 \times 10^4$ $10$