题目描述

IOI 2023 组委会需要规划 Ópusztaszer 之旅，当地有 $N$ 个地标（编号 $0$ 到 $N-1$），部分地标间连有双向道路，且组委会不知道具体连接情况，但已知存在正整数 $D$（$D \le 3$），使得路网密度至少为 $D$。

路网密度定义

若对所有满足 $0 \le u < v < w < N$ 的地标三元组 $(u, v, w)$，其两两配对 $(u,v)$、$(v,w)$、$(u,w)$ 中至少有 $\delta$ 条道路相连，则称路网密度至少为 $\delta$。

询问规则

组委会可通过调用 are_connected 函数询问接线员，每次询问需满足：

1. 给出两个非空数组 $A = [A[0], \ldots, A[P-1]]$ 和 $B = [B[0], \ldots, B[R-1]]$；
2. 数组内元素两两不同（$A$ 中无重复，$B$ 中无重复）；
3. $A$ 与 $B$ 无交集（所有 $A[i] \neq B[j]$）。

接线员的返回结果为：若存在 $A[i]$ 与 $B[j]$ 之间有道路，则返回 true；否则返回 false。

最长路程定义

• 路程：由不同地标构成的序列 $t[0], t[1], \ldots, t[l-1]$，满足对所有 $0 \le i < l-2$，$t[i]$ 与 $t[i+1]$ 间有道路。
• 最长路程：若不存在长度至少为 $l+1$ 的路程，则长度为 $l$ 的路程是最长路程。

你的任务是通过询问，找到一条最长路程并返回其地标序列。

实现细节

需在程序开始引入库 longesttrip.h，并实现以下函数：

int[] longest_trip(int N, int D)

参数说明

• $N$：地标总数；
• $D$：路网密度的最小值（$1 \le D \le 3$）。

返回要求

• 返回一个数组 $t$，表示某条最长路程的地标序列；
• 若返回数组长度不符要求（如非最长路程）、元素非合法地标编号，将被判错。

可调用函数

bool are_connected(int[] A, int[] B)

调用限制

1. 单次 longest_trip 调用中，are_connected 调用次数至多 $32640$ 次；
2. 所有 are_connected 调用累计次数至多 $150000$ 次；
3. 所有调用中，数组 $A$ 和 $B$ 的累计长度之和至多 $1500000$。

例子

例子 1

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

例子 2（$N=4, D=1$）

若路网中道路仅为 $(0,1)$、$(2,3)$，则最长路程长度为 $2$，函数可返回 $[0,1]$、$[2,3]$ 等序列。

约束条件

• $3 \le N \le 256$；
• 所有 longest_trip 调用中，$N$ 的累计总和至多 $1024$；
• $1 \le D \le 3$。

子任务

子任务	附加限制	分值
1	$D=3$	$5$
2	$D=2$	$10$
3	$D=1$，返回路程长度至少为 $\lceil \frac{l^\star}{2} \rceil$（$l^\star$ 为最长路程长度）即可	$25$
4	$D=1$，需返回最长路程，得分与 are_connected 调用次数挂钩	$60$

子任务 4 得分规则

设单次 longest_trip 调用中 are_connected 的最大调用次数为 $q$：

• $2750 < q \le 32640$：$20$ 分；
• $550 < q \le 2750$：$30$ 分；
• $400 < q \le 550$：$45$ 分；
• $q \le 400$：$60$ 分。

评测程序示例

输入格式

1. 第 $1$ 行：$C$（场景数，即 longest_trip 调用次数）；
2. 每个场景描述：
   • 第 $1$ 行：$N \; D$；
   • 第 $1+i$ 行（$1 \le i < N$）：数组 $U_i$（长度 $i$），$U_i[j] = 1$ 表示地标 $j$ 与 $i$ 有道路，$U_i[j] = 0$ 表示无道路。

输出格式

1. 若路网密度不足 $D$，输出 Insufficient Density 并中止；
2. 若存在调用违规（如数组无效、询问次数超限），输出 Protocol Violation: <MSG>；
3. 每个场景的合法结果：
   • 第 $1$ 行：返回路程的长度 $l$；
   • 第 $2$ 行：返回的地标序列；
   • 第 $3$ 行：该场景中 are_connected 的调用次数；
4. 最后一行：所有 longest_trip 调用中 are_connected 的最大调用次数。