Background

IOI 2023 D1T2.

Special reminder: Due to the special nature of Luogu's interactive mechanism, you cannot include header files in your program. Instead, you must paste the contents of the header file at the beginning of your source file. That is, add the following lines at the start of your program:

#include <vector>

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

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

Problem Description

The IOI 2023 organizing committee is in big trouble! They forgot to plan the upcoming trip to Ópusztaszer. However, maybe it is not too late yet......

In Ópusztaszer, there are $N$ landmarks, numbered from $0$ to $N-1$. Some pairs of landmarks are connected by two-way roads. Between any pair of landmarks, there is at most one road. The committee does not know which pairs of landmarks are connected by roads.

If, for every three distinct landmarks, there are at least $\delta$ roads among them, we say that the road network density of Ópusztaszer is at least $\delta$. In other words, for every triple of landmarks $(u, v, w)$ with $0 \le u \lt v \lt w \lt N$, among the pairs $(u,v)$, $(v,w)$, and $(u,w)$, at least $\delta$ of these pairs are connected by a road.

The committee knows that there exists a positive integer $D$ such that the road network density is at least $D$. Note that $D$ will not be greater than $3$.

The committee can query the telephone operator in Ópusztaszer to obtain information about road connections between some landmarks. In each query, you must provide two non-empty arrays of landmarks $[A[0], \ldots, A[P-1]]$ and $[B[0], \ldots, B[R-1]]$. All landmarks must be pairwise distinct, i.e.:

• For all $i$ and $j$ with $0 \le i \lt j \lt P$, we have $A[i] \neq A[j]$.
• For all $i$ and $j$ with $0 \le i \lt j \lt R$, we have $B[i] \neq B[j]$.
• For all $i$ with $0 \le i \lt P$ and $j$ with $0 \le j \lt R$, we have $A[i] \neq B[j]$.

For each query, the operator reports whether there exists a road connecting some landmark in $A$ with some landmark in $B$. More precisely, the operator checks all pairs $i$ and $j$ with $0 \le i \lt P$ and $0 \le j \lt R$. If there exists a road between $A[i]$ and $B[j]$ for at least one such pair, the operator reports true. Otherwise, the operator reports false.

A trip of length $l$ is defined as a sequence of distinct landmarks $t[0], t[1], \ldots, t[l-1]$ such that for all $i$ from $0$ to $l-2$ (inclusive), there is a road connecting landmarks $t[i]$ and $t[i+1]$. If there is no trip of length at least $l+1$, then a trip of length $l$ is called a longest trip.

Your task is to help the committee find a longest trip in Ópusztaszer by querying the operator.

[Implementation Details]

You need to implement the following function:

int[] longest_trip(int N, int D)

• $N$: the number of landmarks in Ópusztaszer.
• $D$: the guaranteed minimum value of the road network density.
• This function should return an array representing a longest trip $t = [t[0], t[1], \ldots, t[l-1]]$.
• For each test case, this function may be called multiple times.

The above function may call the following function:

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

• $A$: a non-empty array of landmarks with all elements pairwise distinct.
• $B$: a non-empty array of landmarks with all elements pairwise distinct.
• $A$ and $B$ must be disjoint.
• This function returns true if there exists a road connecting some landmark in $A$ and some landmark in $B$. Otherwise, it returns false.
• In each call to longest_trip, this function may be called at most $32\,640$ times. The total number of calls across all invocations is at most $150\,000$.
• If we sum up the lengths of arrays $A$ and $B$ over all calls, the total combined length must not exceed $1\,500\,000$.

The grader is non-adaptive. Each submission is evaluated on the same set of test cases. In other words, for each test case, the values of $N$ and $D$, as well as the pairs of landmarks connected by roads, remain the same for every call to longest_trip.

Hint

[Examples]

Sample 1

Consider a scenario with $N = 5$, $D = 1$, where the roads are connected as shown in the figure below:

The function longest_trip is called as follows:

longest_trip(5, 1)

This function may call are_connected as follows.

After the fourth call, we know that among $(1,4)$, $(0,4)$, $(1,3)$, and $(0,3)$, none of these pairs of landmarks is connected by a road. Since the road network density is at least $D = 1$, from the triple $(0, 3, 4)$ we can conclude that the pair $(3,4)$ must be connected by a road. Similarly, landmarks $0$ and $1$ must be connected.

At this point, we can conclude that $t = [1, 0, 2, 3, 4]$ is a trip of length $5$, and there is no trip of length greater than $5$. Therefore, the function longest_trip may return $[1, 0, 2, 3, 4]$.

Consider another scenario with $N = 4$, $D = 1$, where the roads between landmarks are as shown in the figure below:

The function longest_trip is called as follows:

longest_trip(4, 1)

In this scenario, the longest trip has length $2$. Therefore, after a small number of calls to are_connected, the function longest_trip may return any of $[0, 1]$, $[1, 0]$, $[2, 3]$, and $[3, 2]$.

Sample 2

Subtask 0 contains another test case used as an example, with $N = 256$ landmarks.

[Constraints]

• $3 \le N \le 256$.
• For each test case, across all calls to longest_trip, the total sum of $N$ does not exceed $1\,024$.
• $1 \le D \le 3$.

[Subtasks]

1. (5 points) $D = 3$.
2. (10 points) $D = 2$.
3. (25 points) $D = 1$. Let $l^\star$ denote the length of the longest trip. The function longest_trip does not need to return a trip of length $l^\star$, but should return a trip of length at least $\left\lceil \frac{l^\star}{2} \right\rceil$.
4. (60 points) $D = 1$.

In subtask 4, your score depends on the number of calls to are_connected made during a single call to longest_trip. Let $q$ be the maximum number of are_connected calls over all calls to longest_trip across all test cases in this subtask. Your score for this subtask is computed according to the following table:

If, on some test case, the calls to are_connected do not follow the limits given in the implementation details section, or the array returned by longest_trip is incorrect, your score for this subtask will be $0$.

[Sample Grader]

Let $C$ be the number of scenarios, i.e. the number of calls to longest_trip. The sample grader reads input data in the following format:

• Line $1$: $C$.

Then follow the descriptions of these $C$ scenarios.

For each scenario, the sample grader reads data in the following format:

• Line $1$: $N \; D$.
• Line $1 + i$ ($1 \le i \lt N$): $U_i[0] \; U_i[1] \; \ldots \; U_i[i-1]$.

Here, each $U_i$ ($1 \le i \lt N$) is an array of length $i$, used to specify which pairs of landmarks are connected by roads. For all $i$ and $j$ with $1 \le i \lt N$ and $0 \le j \lt i$:

• If landmarks $j$ and $i$ are connected by a road, then $U_i[j]$ should be $1$.
• If landmarks $j$ and $i$ are not connected by a road, then $U_i[j]$ should be $0$.

In each scenario, before calling longest_trip, the sample grader checks whether the road network density is at least $D$. If this condition is not satisfied, the sample grader outputs Insufficient Density and terminates.

If a rule violation is detected, the sample grader outputs Protocol Violation: <MSG>, where <MSG> is one of the following error messages:

• invalid array: in some call to are_connected, at least one of arrays $A$ and $B$
  • is empty, or
  • contains an element that is not an integer between $0$ and $N-1$ (inclusive), or
  • contains duplicate elements.
• non-disjoint arrays: in some call to are_connected, the intersection of arrays $A$ and $B$ is not empty.
• too many calls: the number of calls to are_connected in the current call to longest trip exceeds $32\,640$, or the total number of calls exceeds $150\,000$.
• too many elements: across all calls to are_connected, the total number of passed landmarks exceeds $1\,500\,000$.

Otherwise, let the array returned by longest_trip in some scenario be $t[0], t[1], \ldots, t[l - 1]$, where $l$ is a non-negative integer. The sample grader outputs three lines for that scenario in the following format:

• Line $1$: $l$.
• Line $2$: $t[0] \; t[1] \; \ldots \; t[l-1]$.
• Line $3$: the number of calls to are_connected made in that scenario.

Finally, the sample grader outputs:

• Line $1 + 3 \cdot C$: the maximum number of times are_connected was called over all invocations of longest_trip.

Translated by ChatGPT 5