QOJ.ac

QOJ

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

# 7791. 通道建设 Passage Construction

Statistics

这是一道交互题。

一场叛乱后,上层政府任命你担任这座城市的市长,负责重建。你需要在城市里修建 $ N $ 条通道。

这是一座有着 $ 2N $ 个依次编号为 $ 1,2,\dots,2N $ 街区的大城市,它们由 $ 2N-1 $ 条双向道路连通。换言之,城市的街区和道路构成一棵树。

所有通道都是单向的,你需要选定恰好 $ N $ 个街区作为入口,其余 $ N $ 个街区作为出口。$ N $ 条通道需要不重不漏地覆盖所有入口和出口。同时为了避免上层政府质疑通道的修建方案,不能存在两条通道 $ (a,b),(c,d) $,其中 $ a,c $ 为入口,$ b,d $ 为出口,满足 $ \operatorname{dis}(a,b)<\operatorname{dis}(a,d)<\operatorname{dis}(c,d) $。此处 $ \operatorname{dis}(x,y) $ 定义为街区 $ x $ 到街区 $ y $ 的距离,即最少经过的道路数。

然而叛军烧毁了很多资料,导致你只拥有一份年代久远的城市地图。现在的城市相较于你手上的地图描绘的城市早已经过了许多次扩建。你的地图只有现在的城市的街区 $ 1\dots N $ 和当时连通它们的 $ N-1 $ 条道路。但扩建不会破坏城市的布局:对扩建前的两条恰有一个公共街区的道路 $ (a,b),(b,c) $,扩建后 $ a $ 到 $ b $ 的最短路径和 $ b $ 到 $ c $ 的最短路径依旧只有一个公共街区 $ b $。

由于你暂时人手不足,你只有以下两种渠道收集信息:

  1. 给定一系列街区 $ A $ 和一系列街区 $ B $(需要满足 $ |B|>1 $),对 $ A $ 中每个街区 $ x $,你可以知道离 $ x $ 最远的在所有路径 $ (x,y)(y\in B) $ 上的街区(即以 $ x $ 为根时 $ B $ 中街区的 $ \operatorname{LCA} $)是否为一个给定点 $ P $。
  2. 给出两个街区 $ x,y $,你可以知道 $ \operatorname{dis}(x,y) $。

请完成修建通道的任务。

实现细节

你不需要,也不应当实现主函数。

你应当引入头文件 passageconstruction.h

你应当实现如下函数:

std::vector<std::pair<int,int>> ConstructPassages(int N, const std::vector<std::pair<int,int>> &E);

$ N $ 的含义如题目所述,$ E $ 为你的地图上的道路,你需要返回恰好 $ N $ 个pair,代表一组合法的修建方案。一个 pair 代表一条通道,其成员 first 为入口,second 为出口。特别地,如果无解,请返回一个空vector

可调用函数:

std::vector<int> QueryLCA(const std::vector<int> &A, const std::vector<int> &B, int P);

该函数代表一次操作 $ 1 $,$ A,B,P $ 的含义如上文所述。保证返回vector 的大小与A.size()相同,值只包含 $ 0 $ 和 $ 1 $,第 $ k $ 项(从 $ 0 $ 开始)为 $ 1 $ 当且仅当以 $ A_k $ 为根时 $ B $ 中街区的 $ \operatorname{LCA} $ 为 $ P $。

int GetDistance(int x,int y);

查询距离,$ x,y $ 含义如上文所述。

int getSubtaskID();

获取子任务编号。在样例交互库中该函数恒返回 $ 0 $。

保证城市在交互开始时已经确定,即交互库不自适应。

样例交互库

下发了 sample_grader.cpppassageconstruction.h,你可以使用命令 g++ sample_grader.cpp <your source file> -o passageconstruction -O2 -std=c++14 生成可执行文件。

注意评测时交互库与样例交互库有所不同。

输入格式

第一行一个数 $ N $,含义如题目所述。

接下来 $ 2N-1 $ 行,每行两个数,代表城市的一条道路。注意 $ 1,2,\dots,N $ 需要满足前文所述的条件。

注意样例交互库不会检查输入文件是否合法,输入不合法时其行为未定义。

输出格式

交互库会在运行过程正常结束且答案正确时返回 $ 0 $,答案错误或交互错误时返回 $ 1 $。

当答案错误或交互错误时的提示信息如下:

Index out of range:街区编号不为 $ [1,2N] $ 内的整数。

Invalid construction plan:返回方案格式有误。

Condition not satisfied:返回方案不满足上文的条件。

Invalid type 1 query:执行操作 $ 1 $ 时未满足 $ |B|>1 $ 的条件。

当答案正确时的提示信息如下:

Accepted with a+b operations, sum of size(s)=c+d。其中 $ a,b $ 分别为操作 $ 1 $ 和操作 $ 2 $ 的次数,$ c=\sum |A|,d=\sum |B| $。

当无解时的提示信息如下:

Reported no solution with a+b operations, sum of size(s)=c+d。$ a,b,c,d $ 含义同上。

数据范围

记 $ C_1 $ 为操作 $ 1 $ 次数,$ C_2 $ 为操作 $ 2 $ 次数,$ S_1=\sum |A|,S_2=\sum |B| $。

子任务编号分值$ N\le $$ C_1 $ 上限$ C_2 $ 上限$ S_1 $ 上限$ S_2 $ 上限特殊性质
1$ 3 $$ 5 $$ 100 $$ 100 $$ 1\times10^4 $$ 1\times10^4 $
2$ 6 $$ 100 $$ 2\times 10^4 $$ 1\times10^4 $$ 2\times 10^5 $$ 2\times 10^5 $
3$ 8 $$ 1000 $$ 1\times10^5 $$ 4000 $$ 2\times 10^5 $$ 2\times 10^5 $A
4$ 9 $$ 1000 $$ 1\times10^5 $$ 4000 $$ 2\times 10^5 $$ 2\times 10^5 $BC
5$ 11 $$ 1000 $$ 5\times10^4 $$ 4000 $$ 2\times 10^5 $$ 1\times 10^5 $B
6$ 12 $$ 1000 $$ 2.5\times 10^4 $$ 4000 $$ 2\times 10^5 $$ 1\times 10^5 $C
7$ 14 $$ 1000 $$ 2.5\times 10^4 $$ 4000 $$ 2\times 10^5 $$ 1\times 10^5 $
8$ 10 $$ 5000 $$ 5\times 10^4 $$ 1\times 10^5 $$ 5\times 10^5 $$ 2\times 10^5 $
9$ 27 $$ 5000 $$ 1.5\times 10^4 $$ 1\times 10^4 $$ 2\times 10^5 $$ 5\times 10^4 $

特殊性质 A:城市的每个街区至多与两条道路直接连接。

特殊性质 B:城市的每个街区至多与三条道路直接连接。

特殊性质 C:保证你拥有的地图上的所有道路仍然存在。

评分方式:在一个子任务内,如果 $ C_1,C_2,S_1,S_2 $ 均 $ \le $ 对应上限,该子任务得满分。

否则设对应上限分别为 $ C_1^{Lim},C_2^{Lim},S_1^{Lim},S_2^{Lim} $,令 $ v=\max(\frac{C_1}{C_1^{Lim}},\frac{C_2}{C_2^{Lim}},\frac{S_1}{S_1^{Lim}},\frac{S_2}{S_2^{Lim}}) $。如果 $ v>2 $ 则该子任务得 $ 0 $ 分,否则该子任务得分为该子任务满分分值$ \times (1.4-0.5v)^2 $。

保证交互库运行时间在给定数据范围内 $ \le 0.1\text{s} $,空间 $ \le 64\text{MiB} $。子任务 $ 1\sim 7 $ 的时间限制为 $ 1\text{s} $,其余子任务的时间限制为 $ 2.4\text{s} $。