P15363 [CTS 2026] Ferry (No testdata yet)

There are $n$ islands scattered across the sea, with a total of $m$ undirected routes between the islands. Route $i$ ($1 \le i \le m$) connects islands $u_i$ and $v_i$, and there is a ferry shuttling back and forth on this route. Each ferry has an initial docking position. For the ferry on route $i$ ($1 \le i \le m$): - If $w_i = 0$, then the ferry initially docks at island $u_i$. - If $w_i = 1$, then you may freely decide whether the ferry initially docks at island $u_i$ or island $v_i$. Now there are $k$ travelers. Traveler $j$ ($1 \le j \le k$) initially is on island $s_j$ and needs to go to island $t_j$. Travelers can move only by using ferries. Specifically, each move chooses a traveler $j$ ($1 \le j \le k$) and a route $i$ ($1 \le i \le m$), such that traveler $j$ and the ferry on route $i$ are currently on the same island. Then the traveler boards the ferry and moves together with the ferry to the other endpoint island of route $i$. For example, if traveler $j$ and the ferry on route $i$ are both at island $u_i$, then after the move, both the traveler and the ferry arrive at island $v_i$, and vice versa. You need to determine whether it is possible, through a sequence of traveler moves, to make all travelers reach their respective destinations. If it is possible, you also need to provide one specific sequence of moves. ### 【Implementation Details】 Contestants do not need to, and should not, implement the `main` function. Contestants must ensure that the submitted program includes the header file `ferry.h`, i.e., add the following code at the beginning: ```cpp #include "ferry.h" ``` Contestants need to implement the following function in the submitted source file: ```cpp void ferry(int n, int m, int k, std::vector u, std::vector v, std::vector w, std::vector s, std::vector t); ``` - $n, m, k$ denote the number of islands, the number of routes, and the number of travelers, respectively. - For $0 \le i < m$, $u_i, v_i$ denote the two islands connected by route $i+1$, and $w_i$ indicates whether the initial docking position of the ferry on this route is fixed; see 【Description】 for details. - For $0 \le j < k$, $s_j, t_j$ denote the initial island and the destination island of traveler $j+1$, respectively. - For each test point, this function will be called exactly once by the interaction library. Contestants can report whether it is possible, through a sequence of traveler moves, to make all travelers reach their destinations, by calling the following function: ```cpp void report(bool o); ``` - If $o$ is `true`, it means it is possible to make all travelers reach their destinations through a sequence of moves; if $o$ is `false`, it means it is not possible. - Contestants must ensure that when the interaction library calls `ferry`, this function is called exactly once. Contestants can perform one move by calling the following function: ```cpp void move(int j, int i); ``` - $j, i$ are the indices of the chosen traveler and route, with the meaning as in 【Description】. Contestants must ensure $1 \le j \le k$, $1 \le i \le m$, and that traveler $j$ and the ferry on route $i$ are currently on the same island. In particular, if the initial docking position of the ferry on route $i$ has not been determined yet, and traveler $j$ is on one of the two islands connected by route $i$, then the ferry’s initial docking position is directly determined to be the island where traveler $j$ is. - Contestants must ensure that for each call to `ferry`, the interaction library sees at most $10^6$ calls to this function, and that all calls to this function happen after calling `report`, and the return value of `report` must be `true`. **Note**: In all cases, the time required for the interaction library to run will not exceed $0.1$ seconds. The memory it uses is of fixed size and will not exceed $64$ MiB. ### 【How to Run the Test Program】 `grader.cpp` in the problem directory is a reference implementation of the interaction library. The interaction library used in the final evaluation is different from this reference implementation, so your solution should not depend on the interaction library implementation. You can compile an executable in this problem directory using the following command: ```bash g++ grader.cpp ferry.cpp -o ferry -std=gnu++14 -O2 -pipe -static -s ```

For the compiled executable program: - The executable will read data from standard input in the following format: - The first line contains three positive integers $n, m, k$, representing the number of islands, the number of routes, and the number of travelers. - The $i+1$-th line ($1 \le i \le m$) contains three non-negative integers $u_i, v_i, w_i$, representing the two islands connected by route $i$ and whether the initial docking position of the ferry on this route is fixed; see 【Description】 for details. - The $n+2$-th line contains $k$ positive integers $s_1, \dots, s_k$, representing the initial island of each traveler. - The $n+3$-th line contains $k$ positive integers $t_1, \dots, t_k$, representing the destination island of each traveler.

- The executable will output data to standard output in the following format: - The first line contains a string **Yes** or **No**, indicating whether it is possible, through a sequence of traveler moves, to make all travelers reach their destinations. - If it is possible, then: - The second line contains a non-negative integer $c$, the number of moves. - The $l+2$-th line ($1 \le l \le c$) contains two positive integers $j, i$, indicating the traveler index and the route index chosen in the $l$-th move.

### 【Explanation for Sample 1】 - Initially, traveler 1 is on island 1, and traveler 2 is on island 4. - After the first move, traveler 2 moves together with the ferry on route 5 to island 3. - After the second move, traveler 2 moves together with the ferry on route 3 to island 2. - In the third move, the initial docking position of the ferry on route 1 is determined to be island 1. After the move, traveler 1 moves together with the ferry on route 1 to island 2. - After the fourth move, traveler 1 moves together with the ferry on route 3 to island 3. ### 【Additional Files】 In the additional files: 1. `grader.cpp` is the provided reference implementation of the interaction library. 2. `ferry.h` is the header file; contestants do not need to care about its specific content. 3. `template_ferry.cpp` is the provided sample code; contestants may refer to it and implement their own code. ### 【Subtasks】 For all test data, it holds that: - $2 \le n \le 2,000$, $1 \le m \le 10^4$, $1 \le k \le 10^2$. - For all $1 \le i \le m$, $1 \le u_i, v_i \le n$, $u_i \ne v_i$, $w_i \in \{0,1\}$. - For all $1 \le i \le k$, $1 \le s_i, t_i \le n$. ::cute-table{tuack} | Subtask ID | Score | Special Property | |:-:|:-:|:-:| | $1$ | $6$ | $k = 1$ | | $2$ | $7$ | $k = n$, and $s_1, \dots, s_n$ and $t_1, \dots, t_n$ are both permutations of $1 \sim n$ | | $3$ | $11$ | For all $1 \le i \le m$, $w_i = 0$ | | $4$ | $9$ | For all $1 \le i \le m$, $w_i = 1$ | | $5$ | $29$ | There exists a permutation $p$ of $1 \sim k$ such that for all $1 \le i \le k$, $s_i = t_{p_i}$ | | $6$ | $26$ | $n \le 100$, $m \le 200$, $k \le 60$ | | $7$ | $12$ | None | ### 【Scoring】 **Note**: - Contestants must not obtain internal information of the interaction library through illegal means, such as directly interacting with standard input or output streams. Such behavior will be considered cheating. - The interaction library used in the final evaluation is different from the sample interaction library. This problem is first subject to the same limits as traditional problems. For example, a compilation error will cause the entire problem to get 0 points; runtime error, time limit exceeded, memory limit exceeded, etc., will cause the corresponding test points to get 0 points. Contestants may access only variables they define themselves and variables provided by the interaction library. Attempting to access other address spaces may cause compilation errors or runtime errors. Each time the `ferry` function is called, if the `report` function or the `move` function is called illegally, or the number of calls to `move` exceeds $10^6$, then the corresponding test point will get 0 points. Based on the above conditions: - For each test point, if the return value of `report` is correct, you can get 40% of the score. On top of that, if `report` returns `false`, or when the `ferry` function returns all travelers have reached their corresponding destination islands, you can get full score. Translated by ChatGPT 5