题目描述
IOI 2023 组委会有大麻烦了!他们忘记计划即将到来的 Ópusztaszer 之旅了。然而,或许一切尚未为晚 ......
在 Ópusztaszer 有
如果对于每三个不同的地标,它们之间都至少连有
组委会已知有某个正整数
组委会可以询问 Ópusztaszer 的电话接线员,以获取关于某些地标之间的道路连接信息。在每次询问时,必须给出两个非空的地标数组
- 对于满足
的所有 和 ,有 ; - 对于满足
的所有 和 ,有 ; - 对于满足
且 的所有 和 ,有 。
对每次询问,接线员都会报告是否存在 true
。否则,接线员将报告 false
。
一条长度为
你的任务是通过询问接线员,帮助组委会在 Ópusztaszer 找一条最长路程。
实现细节
你需要引用头文件 longesttrip.h
。
你需要实现如下函数:
int[] longest_trip(int N, int D)
:Ópusztaszer 的地标数量。 :可以保证的路网密度最小值。- 该函数需要返回一个表示某条最长路程的数组
。 - 对于每个测试用例,该函数都可能会被调用 多次。
上述函数可以调用如下函数:
bool are_connected(int[] A, int[] B)
:一个非空、且元素两两不同的地标数组。 :一个非空、且元素两两不同的地标数组。 和 之间应无交集。- 如果存在连接
中某个地标以及 中某个地标的道路,该函数返回true
。否则该函数返回false
。 - 在每次
longest_trip
调用中,该函数可以被至多调用 次。该函数的累计调用总数至多为 次。 - 对历次调用该函数时传递的数组
和 长度进行累计,两个数组累计长度加起来不能超过 。
评测程序是非适应性的。每次提交都将在同一组测试用例上进行评测。换言之,在每个测试用例中,longest_trip
调用都保持不变。
例子
样例一
考虑某个
函数 longest_trip
被调用如下:
longest_trip(5, 1)
该函数可以调用 are_connected
如下。
调用 | 有道路连接的配对 | 返回值 |
---|---|---|
are_connected([0], [1, 2, 4, 3]) |
true |
|
are_connected([2], [0]) |
true |
|
are_connected([2], [3]) |
true |
|
are_connected([1, 0], [4, 3]) |
无 | false |
在第四次调用后,可知
至此,可以总结出 longest_trip
可以返回
考虑另一个场景, 其中
函数 longest_trip
被调用如下:
longest_trip(4, 1)
在这个场景中,最长路程的长度为 are_connected
进行少量调用后,函数 longest_trip
可以返回
样例 2
子任务 0 包含另一个测试用例用作示例,其中有
数据范围
- 对于每个测试用例,函数
longest_trip
的所有调用中 的累计总和不超过 。
子任务
- (5 分)
- (10 分)
- (25 分)
。令 表示最长路程的长度。函数longest_trip
不必返回长度为 的某条路程,而应返回长度至少为 的某条路程。 - (60 分)
在子任务 4 中,你的得分将根据 longest_trip
的单次调用中对函数 are_connected
的调用数量而定。对该子任务的所有测试用例调用 longest_trip
,令 are_connected
调用次数的最大值。
你在该子任务上的得分将按照下表进行计算:
条件 | 得分 |
---|---|
如果在某个测试用例上,对函数 are_connected
的调用没有遵守实现细节部分给出的限制条件,或者 longest_trip
返回的数组是错误的,你的解答在该子任务上的得分将为
评测程序示例
令 longest_trip
的次数。
评测程序示例读取如下格式的输入数据:
- 第
行:
接下来是这
评测程序示例读取每个场景如下格式的描述数据:
- 第
行: - 第
行( ):
这里每个
- 如果地标
和 之间有道路相连,则 的值应为 ; - 如果地标
和 之间没有道路相连,则 的值应为 。
在每个场景中,在调用 longest_trip
之前,评测程序示例检查路网的密度是否至少为 Insufficient Density
并中止。
如果检查出违反规则的行为,评测程序示例的输出为 Protocol Violation: <MSG>
,这里 <MSG>
为如下错误信息之一:
invalid array
:在are_connected
的某次调用中,数组 和 中至少其一- 为空,或
- 有元素不是
到 之间(包含 和 )的整数,或 - 有重复元素。
non-disjoint arrays
:在are_connected
的某次调用中,数组 和 的交集不空。too many calls
:函数are_connected
在longest trip
的当前调用中的被调用次数超过了 ,或者其累计调用次数超过了 。too many elements
:在are_connected
的全部调用中,所传递的地标的累计数量超过了 。
否则,令 longest_trip
函数在某个场景中的返回数组为
- 第
行: - 第
行: - 第
行:在该场景中调用are_connected
的次数
最后,评测程序示例输出:
- 第
行:在longest_trip
的所有调用中,函数are_connected
被调用的最多次数
关于 Hack 格式
请在第一行数据组数前加上数据类型 D3/D2/D1Half/D1
。
时间限制:
空间限制: