{"raw_statement":[{"iden":"background","content":"IOI2023 D1T2\n\n**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引入头文件，而需要把头文件的内容加入文件的开头。即，在程序开头加入以下几行语句：**\n\n```\n#include <vector>\n\nstd::vector<int> longest_trip(int N, int D);\n\nbool are_connected(std::vector<int> A, std::vector<int> B);\n```"},{"iden":"statement","content":"IOI 2023 组委会有大麻烦了！他们忘记计划即将到来的 Ópusztaszer 之旅了。然而，或许一切尚未为晚 ......\n\n在 Ópusztaszer 有 $N$ 个地标，编号为从 $0$ 到 $N-1$。某些地标之间连有**双向**的**道路**。任意一对地标之间至多连有一条道路。组委会**不知道**哪些地标之间有道路相连。\n\n如果对于每三个不同的地标，它们之间都至少连有 $\\delta$ 条道路，我们就称 Ópusztaszer 的路网**密度**是**至少**为 $\\delta$ 的。换言之，对所有满足 $0 \\le u \\lt v \\lt w \\lt N$ 的地标三元组 $(u, v, w)$，配对 $(u,v)$，$(v,w)$ 和 $(u,w)$ 中至少有 $\\delta$ 个配对中的地标有道路相连。\n\n组委会**已知**有某个正整数 $D$，满足路网密度至少为 $D$。注意， $D$ 的值不会大于 $3$。\n\n组委会可以**询问** Ópusztaszer 的电话接线员，以获取关于某些地标之间的道路连接信息。在每次询问时，必须给出两个非空的地标数组 $[A[0], \\ldots, A[P-1]]$ 和 $[B[0], \\ldots, B[R-1]]$。地标之间必须是两两不同的，即，\n\n* 对于满足 $0 \\le i \\lt j \\lt P$ 的所有 $i$ 和 $j$，有 $A[i] \\neq A[j]$；\n* 对于满足 $0 \\le i \\lt j \\lt R$ 的所有 $i$ 和 $j$，有 $B[i] \\neq B[j]$；\n* 对于满足 $0 \\le i \\lt P$ 且 $0\\le j \\lt R$ 的所有 $i$ 和 $j$，有 $A[i] \\neq B[j]$。\n\n对每次询问，接线员都会报告是否存在 $A$ 中的某个地标和 $B$ 中的某个地标有道路相连。更准确地说，接线员会对满足 $0 \\le i \\lt P$ 和 $0\\le j \\lt R$ 的所有配对 $i$ 和 $j$ 进行尝试。如果其中某对地标 $A[i]$ 与 $B[j]$ 之间连有道路，接线员将报告 `true`。否则，接线员将报告 `false`。\n\n一条长度为 $l$ 的**路程**，被定义为由**不同**地标 $t[0], t[1], \\ldots, t[l-1]$ 构成的序列，其中对从 $0$ 到 $l-2$（包括 $0$ 和 $l-2$）的所有 $i$，地标 $t[i]$ 和 $t[i+1]$ 之间都有道路相连。如果不存在长度至少为 $l+1$ 的路程，则长度为 $l$ 的某条路程被称为是**最长路程**。\n\n你的任务是通过询问接线员，帮助组委会在 Ópusztaszer 找一条最长路程。\n\n---\n\n**【实现细节】**\n\n你需要实现如下函数：\n\n```\nint[] longest_trip(int N, int D)\n```\n\n* $N$：Ópusztaszer 的地标数量。\n* $D$：可以保证的路网密度最小值。\n* 该函数需要返回一个表示某条最长路程的数组 $t = [t[0], t[1], \\ldots, t[l-1]]$。\n* 对于每个测试用例，该函数都可能会被调用 **多次**。\n\n上述函数可以调用如下函数：\n\n```\nbool are_connected(int[] A, int[] B)\n```\n\n* $A$：一个非空、且元素两两不同的地标数组。\n* $B$：一个非空、且元素两两不同的地标数组。\n* $A$ 和 $B$ 之间应无交集。\n* 如果存在连接 $A$ 中某个地标以及 $B$ 中某个地标的道路，该函数返回 `true`。否则该函数返回 `false`。\n* 在每次 `longest_trip` 调用中，该函数可以被至多调用 $32\\,640$ 次。该函数的累计调用总数至多为 $150\\,000$ 次。\n* 对历次调用该函数时传递的数组 $A$ 和 $B$ 长度进行累计，两个数组累计长度加起来不能超过 $1\\,500\\,000$。\n\n评测程序是**非适应性的**。每次提交都将在同一组测试用例上进行评测。换言之，在每个测试用例中，$N$ 和 $D$ 的值，以及道路所连接的地标配对，对于每次 `longest_trip` 调用都保持不变。"},{"iden":"note","content":"**【例子】**\n\n**样例一**\n\n考虑某个 $N = 5$, $D = 1$ 的场景，其中道路连接情形如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/h4q6u936.png)\n\n函数 `longest_trip` 被调用如下：\n\n```\nlongest_trip(5, 1)\n```\n\n该函数可以调用 `are_connected` 如下。\n\n|                调用                |  有道路连接的配对  | 返回值  |\n| :--------------------------------: | :----------------: | :-----: |\n| `are_connected([0], [1, 2, 4, 3])` | $(0,1)$ 和 $(0,2)$ | `true`  |\n|     `are_connected([2], [0])`      |      $(2,0)$       | `true`  |\n|     `are_connected([2], [3])`      |      $(2,3)$       | `true`  |\n|  `are_connected([1, 0], [4, 3])`   |         无         | `false` |\n\n在第四次调用后，可知 $(1,4)$，$(0,4)$，$(1,3)$ 和 $(0,3)$ 中**没有**哪个配对中的地标之间连有道路。由于路网的密度至少是 $D = 1$，我们由三元组 $(0, 3, 4)$ 可知，配对 $(3,4)$ 的地标之间必须连有道路。与此相似，地标 $0$ 和 $1$ 之间必须是相连的。\n\n至此，可以总结出 $t = [1, 0, 2, 3, 4]$ 是一条长度为 $5$ 的路程，而且不存在长度超过 $5$ 的路程。因此，函数 `longest_trip` 可以返回 $[1, 0, 2, 3, 4]$。\n\n考虑另一个场景， 其中 $N = 4$, $D = 1$，且地标之间的道路如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6kk0r3y9.png)\n\n函数 `longest_trip` 被调用如下：\n\n```\nlongest_trip(4, 1)\n```\n\n在这个场景中，最长路程的长度为 $2$。因此，在对函数 `are_connected` 进行少量调用后，函数 `longest_trip` 可以返回 $[0, 1]$, $[1, 0]$, $[2, 3]$ 和 $[3, 2]$ 中的任意一个.\n\n**样例 2**\n\n子任务 0 包含另一个测试用例用作示例，其中有 $N=256$ 个地标。\n\n**【数据范围】**\n\n* $3 \\le N \\le 256$\n* 对于每个测试用例，函数 `longest_trip` 的所有调用中 $N$ 的累计总和不超过 $1\\,024$。\n* $1 \\le D \\le 3$\n\n**【子任务】**\n\n1. （5 分）$D = 3$\n1. （10 分）$D = 2$\n1. （25 分）$D = 1$。令 $l^\\star$ 表示最长路程的长度。函数 `longest_trip` 不必返回长度为 $l^\\star$ 的某条路程，而应返回长度至少为 $\\left\\lceil \\frac{l^\\star}{2} \\right\\rceil$ 的某条路程。\n1. （60 分）$D = 1$\n\n在子任务 4 中，你的得分将根据 `longest_trip` 的单次调用中对函数 `are_connected` 的调用数量而定。对该子任务的所有测试用例调用 `longest_trip`，令 $q$ 为各次调用产生的函数 `are_connected` 调用次数的最大值。\n你在该子任务上的得分将按照下表进行计算：\n\n|            条件            | 得分 |\n| :------------------------: | :--: |\n| $2\\,750 \\lt q \\le 32\\,640$ | $20$ |\n|   $550 \\lt q \\le 2\\,750$   | $30$ |\n|    $400 \\lt q \\le 550$     | $45$ |\n|        $q \\le 400$         | $60$ |\n\n如果在某个测试用例上，对函数 `are_connected` 的调用没有遵守实现细节部分给出的限制条件，或者 `longest_trip` 返回的数组是错误的，你的解答在该子任务上的得分将为 $0$。\n\n**【评测程序示例】**\n\n令 $C$ 为场景数量，即调用 `longest_trip` 的次数。\n评测程序示例读取如下格式的输入数据：\n\n* 第 $1$ 行：$C$\n\n接下来是这 $C$ 个场景的描述数据。\n\n评测程序示例读取每个场景如下格式的描述数据：\n\n* 第 $1$ 行：$N \\; D$\n* 第 $1 + i$ 行（$1 \\le i \\lt N$）：$U_i[0] \\; U_i[1] \\; \\ldots \\; U_i[i-1]$\n\n这里每个 $U_i$（$1 \\le i \\lt N$）均为长度为 $i$ 的数组，以给出那些有道路相连的地标配对。对于满足 $1 \\le i \\lt N$ 且 $0 \\le j \\lt i$ 的所有 $i$ 和 $j$：\n\n* 如果地标 $j$ 和 $i$ 之间有道路相连，则 $U_i[j]$ 的值应为 $1$；\n* 如果地标 $j$ 和 $i$ 之间没有道路相连，则 $U_i[j]$ 的值应为 $0$。\n\n在每个场景中，在调用 `longest_trip` 之前，评测程序示例检查路网的密度是否至少为 $D$。如果不满足该条件，评测程序示例将输出信息 `Insufficient Density` 并中止。\n\n如果检查出违反规则的行为，评测程序示例的输出为 `Protocol Violation: <MSG>`，这里 `<MSG>` 为如下错误信息之一：\n\n* `invalid array`：在 `are_connected` 的某次调用中，数组 $A$ 和 $B$ 中至少其一\n  - 为空，或\n  - 有元素不是 $0$ 到 $N-1$ 之间（包含 $0$ 和 $N-1$）的整数，或\n  - 有重复元素。\n* `non-disjoint arrays`：在 `are_connected` 的某次调用中，数组 $A$ 和 $B$ 的交集不空。\n* `too many calls`：函数 `are_connected` 在 `longest trip` 的当前调用中的被调用次数超过了 $32\\,640$，或者其累计调用次数超过了 $150\\,000$。\n* `too many elements`：在 `are_connected` 的全部调用中，所传递的地标的累计数量超过了 $1\\,500\\,000$。\n\n否则，令 `longest_trip` 函数在某个场景中的返回数组为 $t[0], t[1], \\ldots, t[l - 1]$，这里 $l$ 为某个非负整数。评测程序示例将对该场景按照如下格式输出三行：\n\n* 第 $1$ 行：$l$\n* 第 $2$ 行：$t[0] \\; t[1] \\; \\ldots \\; t[l-1]$\n* 第 $3$ 行：在该场景中调用 `are_connected` 的次数\n\n最后，评测程序示例输出：\n\n* 第 $1 + 3 \\cdot C$ 行：在 `longest_trip` 的所有调用中，函数 `are_connected` 被调用的最多次数"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}