这是一道交互题
成为鸽王的三个要求之三,高超的跑路技巧。
显而易见,当你咕掉了事情之后,必然会有负责人来找你,只有当你成功跑路,你才算真正地咕咕咕了。
主持人事先交给码农同学一张地图,这张地图上画了
码农同学发现,每条道路要么是红色要么是蓝色,并且有
但是,其余道路到底是红是蓝还不知道,大概是被标注人员咕掉了。码农同学被告知,每一次查询可以指定一条道路并得知这条道路的颜色。
一次跑路应当经过若干条首尾相接的道路。而根据心理学研究,一次合理的跑路应当恰好经过
为了检测码农同学的跑路技巧是否达到要求,主持人要求码农同学在限定查询次数的条件下,在地图上计划一次合理的跑路,即依次给出经过的
三句话题意:
有一个
已知对所有
你需要找到一条由
任务
你需要实现下面的过程:
std::vector<int> find_longer_path(int n, int k)
其中
如果图中不存在这样的路径,你的函数的返回值应当是一个不包含元素的 vector。
你可以调用以下函数和交互库进行交互:
bool query(int u, int v)
表示询问点
评测方式
评测程序示例将读入如下格式的输入数据:
第一行包括两个正整数
接下来
限制与约定
本题的测试用交互库是 adaptive 的,即图中所有边的颜色可能不会事先确定,而是会根据你的询问对图进行调整。
另外,本题在最终测试前会使用最终测试的交互库测试一组符合子任务一范围的样例,但你不会得到这组样例的具体情况。
对于
子任务编号 | 分值 | |||
---|---|---|---|---|
在本题中,本地测试时可以将 graderlib.cpp
和 grader.cpp
一起粘到提交程序之前。
时间限制:
空间限制:
下载
尾声
尽管码农同学代表跳蚤国在鸽王大赛中表现地相当出色,击败了按时到场的所有其他代表选手,但由于鸽子国的代表选手在大赛结束时才到场,因此码农同学仅仅获得了亚军。更糟糕的是,冠军以外的现场颁奖环节也被咕掉了,可怜的码农同学只能空着手回跳蚤国。