P6766 [APIO2020] Fun Tour

This problem only supports the C++ family of languages. When submitting, you **do not need** to include the `fun.h` header file, but you need to declare `int hoursRequired(int,int)` and `int attractionsBehind(int,int)` at the beginning of your program. If you do not understand what this means, you may directly paste the content of `fun.h` to the beginning of your program. The interactive library may return some strange messages if your program terminates abnormally. If the interactive library has other issues, please send a private message to mrsrz.

In the largest theme park in Jakarta, there are $N$ attractions, numbered from $0$ to $N - 1$. These attractions are connected by $N - 1$ bidirectional roads, and between any two attractions there is a unique simple path using these roads. The roads are numbered from $0$ to $N - 2$. Road $i$ connects attraction $A[i]$ and attraction $B[i]$, and traversing this road takes one hour. To avoid congestion, each attraction is connected to at most three roads. You want to find a touring route such that every attraction is visited exactly once. You think it is very boring if you have to pass too many roads when moving from one attraction to the next. To find an interesting route, you plan the visiting order so that the time needed to reach the next attraction is not greater than the time needed to reach the previous attraction. In other words, you want to find a sequence $P[0], P[1], \dots, P[N - 1]$ that contains every integer from $0$ to $N - 1$ exactly once, and for $0 < i < N - 1$, the time needed to go from attraction $P[i]$ to attraction $P[i + 1]$ is not greater than the time needed to go from attraction $P[i - 1]$ to attraction $P[i]$. You do not have the complete map of the park, so you must make some queries to the information center to find an interesting route. You can make at most $Q$ queries. Each query provides two parameters $X$ and $Y$, where $0 \leq X, Y < N$. Each query is one of the following: - How many hours are needed to travel from attraction $X$ to attraction $Y$. In particular, if $X = Y$, the answer is $0$. - How many attractions $Z$ satisfy that, when you want to travel from attraction $X$ to attraction $Z$, you must pass through attraction $Y$. Attraction $Y$ is included in the count. In particular, if $X = Y$, the answer is $N$. You must implement the function `createFunTour`: - `createFunTour(N, Q)` - This function will be called by the grader exactly once. - $N$: an integer representing the number of attractions. - $Q$: an integer representing the maximum number of queries. - This function may call the following two interactive functions: - `hoursRequired(X, Y)` - $X$: an integer representing the index of the first attraction. - $Y$: an integer representing the index of the second attraction. - This function returns an integer representing the number of hours needed to travel from attraction $X$ to attraction $Y$. - If the value of $X$ or $Y$ is not in the range $0$ to $N - 1$, this test will be judged as Wrong Answer. - `attractionsBehind(X, Y)` - $X$: an integer representing the index of the first attraction. - $Y$: an integer representing the index of the second attraction. - This function returns an integer representing how many attractions $Z$ satisfy that, when you want to travel from attraction $X$ to attraction $Z$, you must pass through attraction $Y$. - If the value of $X$ or $Y$ is not in the range $0$ to $N - 1$, this test will be judged as Wrong Answer. - This function must return an integer sequence of length $N$, representing the visiting order of attractions that you found.

The sample grader reads input in the following format: ``` N Q A[0] B[0] A[1] B[1] . . . A[N-2] B[N-2] ```

If `createFunTour` correctly returns a sequence that satisfies the statement, and the total number of calls to `hoursRequired` and `attractionsBehind` does not exceed $Q$, then the sample grader will output the sequence returned by `createFunTour`. Otherwise, the sample grader will output an error message.

In the example in the figure below, $N = 7$, $Q = 400 000$, $A = [0, 0, 0, 1, 1, 2]$, and $B = [1, 5, 6, 2, 4, 3]$.  The grader will call `createFunTour(7, 400000)`. - If you query `hoursRequired(3, 5)`, the function will return $4$. - If you query `hoursRequired(5, 4)`, the function will return $3$. - If you query `attractionsBehind(5, 1)`, the function will return $4$. From the $5$-th attraction to the $1$-st, $2$-nd, $3$-rd, and $4$-th attractions, you must pass through the $1$-st attraction. - If you query `attractionsBehind(1, 5)`, the function will return $1$. - One valid returned sequence is $[3, 6, 4, 5, 2, 0, 1]$, and the required times to reach the next attraction in order are $[4, 3, 3, 3, 2, 1]$. **Constraints** - $2 \leq N \leq 100 000$. - $Q = 400 000$. - Any two attractions can reach each other through bidirectional roads. - Each attraction is connected to at most three roads. **Subtask $1$ ($10$ points)** - $N \leq 17$. **Subtask $2$ ($16$ points)** - $N \leq 500$. **Subtask $3$ ($21$ points)** - For all $1 \leq i < N$, there is a bidirectional road connecting attraction $i$ and attraction $\lfloor \dfrac{i-1}{2} \rfloor$. **Subtask $4$ ($19$ points)** There exists at least one attraction $T$ such that for all $0 \leq i < N$, `hoursRequired(T, i)` $< 30$, and there exists an integer interval $[L[i], R[i]](0 \leq L[i] \leq i \leq R[i] < N)$ satisfying the following conditions: - Traveling from attraction $T$ to attraction $j$ must pass through attraction $i$ if and only if $L[i] \leq j \leq R[i]$. - If $L[i] < i$, then there is exactly one attraction $X$ such that: - $L[i] \leq X < i$. - There is a road connecting attraction $i$ and attraction $X$. - If $i < R[i]$, then there is exactly one attraction $Y$ such that: - $i < Y \leq R[i]$. - There is a road connecting attraction $i$ and attraction $Y$. **Subtask $5$ ($34$ points)** - No additional constraints. Translated by ChatGPT 5