UOJ Logo Universal Online Judge

UOJ

#486. 【UR #18】在路上了

附件下载 统计

这是一道交互题

成为鸽王的三个要求之三,高超的跑路技巧。

显而易见,当你咕掉了事情之后,必然会有负责人来找你,只有当你成功跑路,你才算真正地咕咕咕了。

主持人事先交给码农同学一张地图,这张地图上画了$n$个城市,依次编号为$1,2,...,n$,每两个城市之间都有一条双向道路连接。

码农同学发现,每条道路要么是红色要么是蓝色,并且有$k-1$条道路已经在地图上被标注为红色,其中第$i$条被标注为红色的道路连接了$i$号城市和$i+1$号城市。

但是,其余道路到底是红是蓝还不知道,大概是被标注人员咕掉了。码农同学被告知,每一次查询可以指定一条道路并得知这条道路的颜色。

一次跑路应当经过若干条首尾相接的道路。而根据心理学研究,一次合理的跑路应当恰好经过$k$条道路和$k+1$个不同城市,且这些道路的颜色都相同。

为了检测码农同学的跑路技巧是否达到要求,主持人要求码农同学在限定查询次数的条件下,在地图上计划一次合理的跑路,即依次给出经过的$k+1$个不同城市的编号。

三句话题意:

有一个 $ n $ 个点的完全图,每条边染红色或蓝色。

已知对所有 $ 1 \le i < k $,连接 $ i $ 和 $ i + 1 $ 的连边为红色。

你需要找到一条由 $ k + 1 $ 个点 $ k $ 条边组成的路径,满足所有边的颜色相同。

任务

你需要实现下面的过程:

std::vector<int> find_longer_path(int n, int k)

其中 $ n $ 是完全图的节点数,$ k $ 是输入的参数。在所有的数据中,保证 $ k \le \frac{2}{3} n $ ,你需要返回一个长度为 $ k + 1 $ 的点的序列,表示你找到的满足条件的路径。

如果图中不存在这样的路径,你的函数的返回值应当是一个不包含元素的 vector。

你可以调用以下函数和交互库进行交互:

bool query(int u, int v)

表示询问点 $ u $ 和点 $ v $ 间的颜色,当函数返回值为 $ \text{true} $ 时表示该连边为红色,否则为蓝色。你需要保证 $ 1 \le u, v \le n $ ,且 $ u \ne v $ 。

评测方式

评测程序示例将读入如下格式的输入数据:

第一行包括两个正整数 $ n $ 和 $ k $;

接下来 $ n $ 行,每行 $ n $ 个数,第 $ i $ 行的第 $ j $ 个数 $ C_{i,j} $ 表示点 $ i $ 和点 $ j $ 间连边的颜色,$ 1 $ 为红色,$ 0 $ 为蓝色。你需要保证 $ C_{i,j} = C_{j, i} $ ,且对所有 $ 1 \le u < k $ ,有 $ C_{u, u + 1} = 1 $ 。

限制与约定

本题的测试用交互库是 adaptive 的,即图中所有边的颜色可能不会事先确定,而是会根据你的询问对图进行调整。

另外,本题在最终测试前会使用最终测试的交互库测试一组符合子任务一范围的样例,但你不会得到这组样例的具体情况。

对于 $ 100 \% $ 的数据,$ 1 \le k \le 2000, \frac{3k}{2} \le n \le 2k $ 。 下表是更详细的数据范围,表中留空代表无特殊限制。

子任务编号$k$$n$$Q$分值
$1$$\le 12$$=160$$13$
$2$$\le 40$$=1600$$7$
$3$$\le 100$$=2k$$=20000$$15$
$4$$\le 500$$=2k$$=2000$$15$
$5$$\le 1000$$=4000$$20$
$6$$\le 2000$$=4000$$30$

交互式类型的题目怎么本地测试

在本题中,本地测试时可以将 graderlib.cppgrader.cpp 一起粘到提交程序之前。

时间限制: $ 2 $s

空间限制: $ 512 $MB

下载

样例及交互库下载

尾声

尽管码农同学代表跳蚤国在鸽王大赛中表现地相当出色,击败了按时到场的所有其他代表选手,但由于鸽子国的代表选手在大赛结束时才到场,因此码农同学仅仅获得了亚军。更糟糕的是,冠军以外的现场颁奖环节也被咕掉了,可怜的码农同学只能空着手回跳蚤国。