UOJ Logo Universal Online Judge

UOJ

#825. 【IOI2023】最长路程

附件下载 统计

题目描述

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

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

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

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

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

  • 对于满足 0i<j<P 的所有 ij,有 A[i]A[j]
  • 对于满足 0i<j<R 的所有 ij,有 B[i]B[j]
  • 对于满足 0i<P0j<R 的所有 ij,有 A[i]B[j]

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

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

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


实现细节

你需要引用头文件 longesttrip.h

你需要实现如下函数:

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

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

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

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

例子

样例一

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

函数 longest_trip 被调用如下:

longest_trip(5, 1)

该函数可以调用 are_connected 如下。

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

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

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

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

函数 longest_trip 被调用如下:

longest_trip(4, 1)

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

样例 2

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

数据范围

  • 3N256
  • 对于每个测试用例,函数 longest_trip 的所有调用中 N 的累计总和不超过 1024
  • 1D3

子任务

  1. (5 分)D=3
  2. (10 分)D=2
  3. (25 分)D=1。令 l 表示最长路程的长度。函数 longest_trip 不必返回长度为 l 的某条路程,而应返回长度至少为 l2 的某条路程。
  4. (60 分)D=1

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

条件 得分
2750<q32640 20
550<q2750 30
400<q550 45
q400 60

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

评测程序示例

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

  • 1 行:C

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

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

  • 1 行:ND
  • 1+i 行(1i<N):Ui[0]Ui[1]Ui[i1]

这里每个 Ui1i<N)均为长度为 i 的数组,以给出那些有道路相连的地标配对。对于满足 1i<N0j<i 的所有 ij

  • 如果地标 ji 之间有道路相连,则 Ui[j] 的值应为 1
  • 如果地标 ji 之间没有道路相连,则 Ui[j] 的值应为 0

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

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

  • invalid array:在 are_connected 的某次调用中,数组 AB 中至少其一
    • 为空,或
    • 有元素不是 0N1 之间(包含 0N1)的整数,或
    • 有重复元素。
  • non-disjoint arrays:在 are_connected 的某次调用中,数组 AB 的交集不空。
  • too many calls:函数 are_connectedlongest trip 的当前调用中的被调用次数超过了 32640,或者其累计调用次数超过了 150000
  • too many elements:在 are_connected 的全部调用中,所传递的地标的累计数量超过了 1500000

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

  • 1 行:l
  • 2 行:t[0]t[1]t[l1]
  • 3 行:在该场景中调用 are_connected 的次数

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

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

关于 Hack 格式

请在第一行数据组数前加上数据类型 D3/D2/D1Half/D1

时间限制:1s

空间限制:2048MB