P9601 [IOI 2023] Longest Trip

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 std::vector longest_trip(int N, int D); bool are_connected(std::vector A, std::vector B); ```

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`.

N/A

N/A

**[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. | Call | Pairs connected by roads | Return value | | :--------------------------------: | :----------------------: | :----------: | | `are_connected([0], [1, 2, 4, 3])` | $(0,1)$ and $(0,2)$ | `true` | | `are_connected([2], [0])` | $(2,0)$ | `true` | | `are_connected([2], [3])` | $(2,3)$ | `true` | | `are_connected([1, 0], [4, 3])` | none | `false` | 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$. 1. (10 points) $D = 2$. 1. (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$. 1. (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: | Condition | Score | | :-------------------------: | :---: | | $2\,750 \lt q \le 32\,640$ | $20$ | | $550 \lt q \le 2\,750$ | $30$ | | $400 \lt q \le 550$ | $45$ | | $q \le 400$ | $60$ | 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: `, where `` 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