P6765 [APIO2020] Swap Cities

This problem only supports the C++ language family. You **do not need** to include the `swap.h` header file when submitting. Due to performance issues of the interactive library itself, the time limit for this problem has been increased to $3$ seconds. If the interactive library has other issues, please message mrsrz privately.

Indonesia has $N$ cities and $M$ bidirectional roads. Cities are numbered from $0$ to $N - 1$, and roads are numbered from $0$ to $M - 1$. Each road connects two different cities. Road $i$ connects city $U[i]$ and city $V[i]$, and a car will consume $W[i]$ units of fuel to travel along this road. Using these roads, any two cities are reachable from each other. Over the next $Q$ days, each day a pair of cities wants to establish political relations. Specifically, on day $j$, city $X[j]$ wants to establish political relations with city $Y[j]$. To do so, city $X[j]$ will send a representative by car to city $Y[j]$. Similarly, city $Y[j]$ will also send a representative by car to city $X[j]$. To avoid congestion, the two cars should not meet at any point in time. More specifically, the two cars cannot be in the same city at the same time. Likewise, the two cars should not travel along the same road in opposite directions at the same time. Also, when a car travels along a road, it must traverse the entire road and arrive at the city on the other end (in other words, a car is not allowed to turn around in the middle of a road). However, a car may visit a city multiple times or traverse a road multiple times. In addition, a car may wait at any city for any amount of time. Because cars with high fuel capacity are expensive, each of the two cities wants to choose a route so that the maximum fuel capacity needed by the two cars is minimized. Each city has a gas station with unlimited supply, so the fuel capacity needed by a car is actually the maximum fuel consumption among the roads it travels. You must implement the functions `init` and `getMinimumFuelCapacity`. - `init(N, M, U, V, W)` - This function will be called by the grader exactly once before any calls to `getMinimumFuelCapacity`. - $N$: An integer representing the number of cities. - $M$: An integer representing the number of roads. - $U$: An integer sequence of length $M$ representing the first endpoint city of each road. - $V$: An integer sequence of length $M$ representing the second endpoint city of each road. - $W$: An integer sequence of length $M$ representing the fuel consumption of each road. - `getMinimumFuelCapacity(X, Y)` - This function will be called by the grader exactly $Q$ times. - $X$: An integer representing the first city. - $Y$: An integer representing the second city. - This function must return an integer, the minimum possible value of the maximum fuel capacity among the two cars that start from city $X$ and city $Y$ respectively and travel to each other’s cities under the rules described above. If it is impossible to satisfy the rules, return $−1$.

The sample grader will read input in the following format: ``` N M U[0] V[0] W[0] U[1] V[1] W[1] . . . U[M-1] V[M-1] W[M-1] Q X[0] Y[0] X[1] Y[1] . . . X[Q-1] Y[Q-1] ```

For each call to `getMinimumFuelCapacity`, the sample grader will output the return value of that function.

In the first sample, $N = 5$, $M = 6$, $U = [0, 0, 1, 1, 1, 2]$, $V = [1, 2, 2, 3, 4, 3]$, $W = [4, 4, 1, 2, 10, 3]$, $Q = 3$, $X = [1, 2, 0]$, $Y = [2, 4, 1]$. As shown in the figure:  The grader will first call `init(5, 6, [0, 0, 1, 1, 1, 2], [1, 2, 2, 3, 4, 3],[4, 4, 1, 2, 10, 3])`. Then the grader will make the following function calls: - `getMinimumFuelCapacity(1, 2)`. First, the car starting from the first city can travel to the third city. Next, the car starting from the second city can travel to the first city, and the car at the third city can travel to the second city. Therefore, the maximum fuel capacity is $3$ (it costs $3$ units of fuel to go from the third city to the second city). There is no better plan, so this function should return $3$. - `getMinimumFuelCapacity(2, 4)`. Any car starting from the fourth city or arriving at the fourth city must consume $10$ units of fuel, so this function should return $10$. - `getMinimumFuelCapacity(0, 1)`. This function should return $4$. In the second sample, $N = 3$, $M = 2$, $U = [0, 0]$, $V = [1, 2]$, $W = [5, 5]$, $Q = 1$, $X = [1]$, $Y = [2]$. As shown in the figure:  The grader will first call `init(3, 2, [0, 0], [1, 2], [5, 5])`, and then the grader will make the following function call: - `getMinimumFuelCapacity(1, 2)`. The two cars cannot satisfy the requirement of not meeting at the same time, so this function should return $-1$. Constraints - $2 \leq N \leq 100 000$. - $N - 1 \leq M \leq 200 000$. - $0 \leq U[i] < V [i] < N$. - Between any two cities, there is at most one road directly connecting them. - Any two cities are reachable from each other via the roads. - $1 \leq W[i] \leq 10^9$. - $1 \leq Q \leq 200 000$. - $0 \leq X[j] < Y [j] < N$. Subtask $1$ ($6$ points) - Each city is an endpoint of at most two roads. Subtask $2$ ($7$ points) - $M = N - 1$. - $U[i] = 0$. Subtask $3$ ($17$ points) - $Q \leq 5$. - $N \leq 1 000$. - $M \leq 2 000$. Subtask $4$ ($20$ points) - $Q \leq 5$. Subtask $5$ ($23$ points) - $M = N - 1$. Subtask $6$ ($27$ points) - No additional constraints. Translated by ChatGPT 5