#P9601. [IOI2023] 最长路程

    ID: 8933 Type: RemoteJudge 1000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: 7 Uploaded By: Tags>2023IOI交互题Special JudgeO2优化

[IOI2023] 最长路程

题目背景

IOI2023 D1T2

特别提醒,由于洛谷交互机制的特殊性,你不能在程序中引入头文件,而需要把头文件的内容加入文件的开头。即,在程序开头加入以下几行语句:

#include <vector>

std::vector<int> longest_trip(int N, int D);

bool are_connected(std::vector<int> A, std::vector<int> B);

题目描述

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

在 Ópusztaszer 有 NN 个地标,编号为从 00N1N-1。某些地标之间连有双向道路。任意一对地标之间至多连有一条道路。组委会不知道哪些地标之间有道路相连。

如果对于每三个不同的地标,它们之间都至少连有 δ\delta 条道路,我们就称 Ópusztaszer 的路网密度至少δ\delta 的。换言之,对所有满足 0u<v<w<N0 \le u \lt v \lt w \lt N 的地标三元组 (u,v,w)(u, v, w),配对 (u,v)(u,v)(v,w)(v,w)(u,w)(u,w) 中至少有 δ\delta 个配对中的地标有道路相连。

组委会已知有某个正整数 DD,满足路网密度至少为 DD。注意, DD 的值不会大于 33

组委会可以询问 Ópusztaszer 的电话接线员,以获取关于某些地标之间的道路连接信息。在每次询问时,必须给出两个非空的地标数组 [A[0],,A[P1]][A[0], \ldots, A[P-1]][B[0],,B[R1]][B[0], \ldots, B[R-1]]。地标之间必须是两两不同的,即,

  • 对于满足 0i<j<P0 \le i \lt j \lt P 的所有 iijj,有 A[i]A[j]A[i] \neq A[j]
  • 对于满足 0i<j<R0 \le i \lt j \lt R 的所有 iijj,有 B[i]B[j]B[i] \neq B[j]
  • 对于满足 0i<P0 \le i \lt P0j<R0\le j \lt R 的所有 iijj,有 A[i]B[j]A[i] \neq B[j]

对每次询问,接线员都会报告是否存在 AA 中的某个地标和 BB 中的某个地标有道路相连。更准确地说,接线员会对满足 0i<P0 \le i \lt P0j<R0\le j \lt R 的所有配对 iijj 进行尝试。如果其中某对地标 A[i]A[i]B[j]B[j] 之间连有道路,接线员将报告 true。否则,接线员将报告 false

一条长度为 ll路程,被定义为由不同地标 t[0],t[1],,t[l1]t[0], t[1], \ldots, t[l-1] 构成的序列,其中对从 00l2l-2(包括 00l2l-2)的所有 ii,地标 t[i]t[i]t[i+1]t[i+1] 之间都有道路相连。如果不存在长度至少为 l+1l+1 的路程,则长度为 ll 的某条路程被称为是最长路程

你的任务是通过询问接线员,帮助组委会在 Ópusztaszer 找一条最长路程。


【实现细节】

你需要实现如下函数:

int[] longest_trip(int N, int D)
  • NN:Ópusztaszer 的地标数量。
  • DD:可以保证的路网密度最小值。
  • 该函数需要返回一个表示某条最长路程的数组 t=[t[0],t[1],,t[l1]]t = [t[0], t[1], \ldots, t[l-1]]
  • 对于每个测试用例,该函数都可能会被调用 多次

上述函数可以调用如下函数:

bool are_connected(int[] A, int[] B)
  • AA:一个非空、且元素两两不同的地标数组。
  • BB:一个非空、且元素两两不同的地标数组。
  • AABB 之间应无交集。
  • 如果存在连接 AA 中某个地标以及 BB 中某个地标的道路,该函数返回 true。否则该函数返回 false
  • 在每次 longest_trip 调用中,该函数可以被至多调用 3264032\,640 次。该函数的累计调用总数至多为 150000150\,000 次。
  • 对历次调用该函数时传递的数组 AABB 长度进行累计,两个数组累计长度加起来不能超过 15000001\,500\,000

评测程序是非适应性的。每次提交都将在同一组测试用例上进行评测。换言之,在每个测试用例中,NNDD 的值,以及道路所连接的地标配对,对于每次 longest_trip 调用都保持不变。

提示

【例子】

样例一

考虑某个 N=5N = 5, D=1D = 1 的场景,其中道路连接情形如下图所示:

函数 longest_trip 被调用如下:

longest_trip(5, 1)

该函数可以调用 are_connected 如下。

调用 有道路连接的配对 返回值
are_connected([0], [1, 2, 4, 3]) (0,1)(0,1)(0,2)(0,2) true
are_connected([2], [0]) (2,0)(2,0)
are_connected([2], [3]) (2,3)(2,3)
are_connected([1, 0], [4, 3]) false

在第四次调用后,可知 (1,4)(1,4)(0,4)(0,4)(1,3)(1,3)(0,3)(0,3)没有哪个配对中的地标之间连有道路。由于路网的密度至少是 D=1D = 1,我们由三元组 (0,3,4)(0, 3, 4) 可知,配对 (3,4)(3,4) 的地标之间必须连有道路。与此相似,地标 0011 之间必须是相连的。

至此,可以总结出 t=[1,0,2,3,4]t = [1, 0, 2, 3, 4] 是一条长度为 55 的路程,而且不存在长度超过 55 的路程。因此,函数 longest_trip 可以返回 [1,0,2,3,4][1, 0, 2, 3, 4]

考虑另一个场景, 其中 N=4N = 4, D=1D = 1,且地标之间的道路如下图所示:

函数 longest_trip 被调用如下:

longest_trip(4, 1)

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

样例 2

子任务 0 包含另一个测试用例用作示例,其中有 N=256N=256 个地标。

【数据范围】

  • 3N2563 \le N \le 256
  • 对于每个测试用例,函数 longest_trip 的所有调用中 NN 的累计总和不超过 10241\,024
  • 1D31 \le D \le 3

【子任务】

  1. (5 分)D=3D = 3
  2. (10 分)D=2D = 2
  3. (25 分)D=1D = 1。令 ll^\star 表示最长路程的长度。函数 longest_trip 不必返回长度为 ll^\star 的某条路程,而应返回长度至少为 l2\left\lceil \frac{l^\star}{2} \right\rceil 的某条路程。
  4. (60 分)D=1D = 1

在子任务 4 中,你的得分将根据 longest_trip 的单次调用中对函数 are_connected 的调用数量而定。对该子任务的所有测试用例调用 longest_trip,令 qq 为各次调用产生的函数 are_connected 调用次数的最大值。 你在该子任务上的得分将按照下表进行计算:

条件 得分
2750<q326402\,750 \lt q \le 32\,640 2020
550<q2750550 \lt q \le 2\,750 3030
400<q550400 \lt q \le 550 4545
q400q \le 400 6060

如果在某个测试用例上,对函数 are_connected 的调用没有遵守实现细节部分给出的限制条件,或者 longest_trip 返回的数组是错误的,你的解答在该子任务上的得分将为 00

【评测程序示例】

CC 为场景数量,即调用 longest_trip 的次数。 评测程序示例读取如下格式的输入数据:

  • 11 行:CC

接下来是这 CC 个场景的描述数据。

评测程序示例读取每个场景如下格式的描述数据:

  • 11 行:N  DN \; D
  • 1+i1 + i 行(1i<N1 \le i \lt N):Ui[0]  Ui[1]    Ui[i1]U_i[0] \; U_i[1] \; \ldots \; U_i[i-1]

这里每个 UiU_i1i<N1 \le i \lt N)均为长度为 ii 的数组,以给出那些有道路相连的地标配对。对于满足 1i<N1 \le i \lt N0j<i0 \le j \lt i 的所有 iijj

  • 如果地标 jjii 之间有道路相连,则 Ui[j]U_i[j] 的值应为 11
  • 如果地标 jjii 之间没有道路相连,则 Ui[j]U_i[j] 的值应为 00

在每个场景中,在调用 longest_trip 之前,评测程序示例检查路网的密度是否至少为 DD。如果不满足该条件,评测程序示例将输出信息 Insufficient Density 并中止。

如果检查出违反规则的行为,评测程序示例的输出为 Protocol Violation: <MSG>,这里 <MSG> 为如下错误信息之一:

  • invalid array:在 are_connected 的某次调用中,数组 AABB 中至少其一
    • 为空,或
    • 有元素不是 00N1N-1 之间(包含 00N1N-1)的整数,或
    • 有重复元素。
  • non-disjoint arrays:在 are_connected 的某次调用中,数组 AABB 的交集不空。
  • too many calls:函数 are_connectedlongest trip 的当前调用中的被调用次数超过了 3264032\,640,或者其累计调用次数超过了 150000150\,000
  • too many elements:在 are_connected 的全部调用中,所传递的地标的累计数量超过了 15000001\,500\,000

否则,令 longest_trip 函数在某个场景中的返回数组为 t[0],t[1],,t[l1]t[0], t[1], \ldots, t[l - 1],这里 ll 为某个非负整数。评测程序示例将对该场景按照如下格式输出三行:

  • 11 行:ll
  • 22 行:t[0]  t[1]    t[l1]t[0] \; t[1] \; \ldots \; t[l-1]
  • 33 行:在该场景中调用 are_connected 的次数

最后,评测程序示例输出:

  • 1+3C1 + 3 \cdot C 行:在 longest_trip 的所有调用中,函数 are_connected 被调用的最多次数