由于某些原因本题仅支持 C++ 各版本语言的提交。
雅加达最大的主题公园中有
你想寻找一条游玩路线并使得每个景点都被参观一次。你认为从一个景点走到下一个景点时经过太多道路是十分无聊的。为了寻找一条有趣的路线,你打算安排景点的参观顺序,使得参观下一个景点所花费的时间不超过参观之前景点所花费的时间。换句话说,你想找到一个序列
你手上没有景点的完整地图,因此你必须向信息中心进行若干次询问才能找到一条有趣路线。你最多能进行
从第
有多少个景点
实现细节
你必须引用 fun.h
头文件。
你必须实现 createFunTour
函数:
std::vector<int> createFunTour(int N, int Q)
该函数将被评测库恰好调用一次。
: 一个整数表示景点的数量。 : 一个整数表示询问次数的最大值。
该函数可以调用以下两个交互函数:
int hoursRequired(int X, int Y)
: 一个整数表示第一个景点的编号。 : 一个整数表示第二个景点的编号。- 该函数将返回一个整数表示从第
个景点到第 个景点需要花费的小时数。 - 如果
或 的值不在 到 的范围内,该测试点将视为答案错误。
int attractionsBehind(int X, int Y)
: 一个整数表示第一个景点的编号。 : 一个整数表示第二个景点的编号。- 该函数将返回一个整数表示有多少个景点
满足,当你想从第 个景点到达第 个景点时一定会经过第 个景点。 - 如果
或 的值不在 到 的范围内,该测试点将视为答案错误。 - 该函数必须返回一个长为
的整数序列,表示你找到的景点参观顺序。
样例评测库
样例评测库将读入以下格式的数据:
N Q A[0] B[0] A[1] B[1] . . . A[N-2] B[N-2]
如果 createFunTour
正确返回了一个满足题意的序列,并且 hoursRequired
和 attractionsBehind
的调用次数总和不超过 createFunTour
得到的序列。其他情况下样例评测库将会输出错误信息。
样例一
input
7 400000 0 1 0 5 0 6 1 2 1 4 2 3
output
3 6 4 5 2 0 1
explanation
在下图的例子中
评测库将调用 createFunTour(7, 400000)
。
如果你询问 hoursRequired(3, 5)
,函数将返回 hoursRequired(5, 4)
,函数将返回 attractionsBehind(5, 1)
,函数将返回 attractionsBehind(1, 5)
,函数将返回
限制与约定
对于
- 任意两个景点间可以通过双向道路互相到达。
- 每个景点至多连接着三条道路。
子任务 ( 分)
子任务 ( 分)
子任务 ( 分)
- 对所有的
,有一条连接着第 个景点与第 个景点的双向道路。
子任务 ( 分)
存在至少一个景点
使得对于所有 ,hoursRequired(T, i)
并且存在一个整数区间 满足下列条件:- 从第
个景点到达第 个景点必须经过第 个景点当且仅当 。 - 若
,则恰有一个景点 满足:- 有一条连接第
个景点与第 个景点的道路。
- 若
,则恰有一个景点 满足:- 有一条连接第
个景点与第 个景点的道路。
- 从第
子任务 ( 分)
- 无附加限制。
子任务 | 依赖的数据包 |
---|---|
1 | 1, 2, 3, 4 |
2 | 1, 2, 3, 4, 5, 6, 7 |
3 | 1, 2, 5, 8 |
4 | 1, 3, 6, 9 |
5 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
实际测试中,前 10 个 subtask 为数据包,后 5 个 subtask 为 5 个子任务。
时间限制:
空间限制: