QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100 Interactive
[+10]

# 4919. Tree

统计

这是一道交互题。

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

V={xuT,xSu}D(T)=iV,jV,i<jd(i,j)

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

实现细节

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

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

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

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

例:

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

数据范围及子任务:

n1000,下面 T 表示你询问次数的上界。

  • A 特殊性质满足:这是一棵二叉树。
  • B 特殊性质满足:树随机,随机方式为:随机生成一个排列p,满足p1=1,然后令fpip1i1内随机生成。
n T 分数 特殊性质
5 1000 5
100 105 5
5000 10
1000 2×105 10
105 10 A
10 B
10
5×104 10 A
10 B
10
3×104 10