#2031. 「IOI 2023」最长路程

IOI 2023 组委会有大麻烦了！他们忘记计划即将到来的 Ópusztaszer 之旅了。然而，或许一切尚未为晚 ......

在 Ó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 调用都保持不变。

例 1

考虑某个 , 的场景，其中道路连接情形如下图所示：

函数 longest_trip 被调用如下：

longest_trip(5, 1)

该函数可以调用 are_connected 如下。

在第四次调用后，可知 ，， 和 中没有哪个配对中的地标之间连有道路。由于路网的密度至少是 ，我们由三元组 可知，配对 的地标之间必须连有道路。与此相似，地标 和 之间必须是相连的。

至此，可以总结出 是一条长度为 的路程，而且不存在长度超过 的路程。因此，函数 longest_trip 可以返回 。

考虑另一个场景， 其中 ，且地标之间的道路如下图所示：

函数 longest_trip 被调用如下：

longest_trip(4, 1)

在这个场景中，最长路程的长度为 。因此，在对函数 are_connected 进行少量调用后，函数 longest_trip 可以返回 , , 和 中的任意一个.

例 2

子任务 包含另一个测试用例用作示例，其中有 个地标。 你可以从比赛系统下载附件包，其中即包含该测试用例。

• 对于每个测试用例，函数 longest_trip 的所有调用中 的累计总和不超过 。

1. （5 分）
2. （10 分）
3. （25 分）。令 表示最长路程的长度。函数 longest_trip 不必返回长度为 的某条路程，而应返回长度至少为 的某条路程。
4. （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 被调用的最多次数