P8375 [APIO2022] Game

This problem only supports C++ submissions. When submitting, you do not need to include the `game.h` header file; you only need to paste the contents of `game.h` from the attachment at the beginning of your code.

The Pharaohs discovered $n$ planets numbered from $0$ to $n - 1$, and built a **one-way teleportation system** between them. In this system, each teleporter connects a start planet and a destination planet. When a tourist uses a teleporter from its start planet, they will arrive at the corresponding destination planet. Note that the start planet and the destination planet may be the same planet. We use $(u, v)$ to denote a teleporter that starts at planet $u$ and ends at planet $v$. To promote the widespread use of the teleportation system, the Pharaohs designed a game for tourists to play while traveling. A tourist may start from any planet. Planets numbered $0, 1, \dots, k - 1$ ($k \le n$) are called **special planets**. Each time the tourist enters a special planet, they obtain one stamp. Currently, for each planet $i$ ($0 \le i \le k - 2$), a teleporter $(i, i + 1)$ has been built. These $k - 1$ teleporters are called **initial teleporters**. Teleporters are continuously built over time. As teleporters are added, it may become possible for a tourist to obtain infinitely many stamps. More precisely, this happens when there exists a planet sequence $w[0], w[1],\dots , w[t]$ satisfying: - $1 \le t$. - $0 \le w[0] \le k - 1$. - $w[t] = w[0]$. - For each $i$ ($0 \le i \le t - 1$), there exists a teleporter $(w[i], w[i + 1])$. Note that a tourist can use both the initial teleporters and any teleporter that has already been built. Your task is to help the Pharaohs check, after each new teleporter is added, whether a tourist can obtain infinitely many stamps. ## Implementation Details You need to implement the following functions: ```cpp init(int n, int k) ``` - $n$: the number of planets. - $k$: the number of special planets. - This function is called exactly once, before any call to `add_teleporter`. ```cpp int add_teleporter(int u, int v) ``` - $u$ and $v$: the start and destination planets of the teleporter being added. - This function is called at most $m$ times (see the “Constraints” section for the range of $m$). - If after adding teleporter $(u, v)$ it is possible for the tourist to obtain infinitely many stamps, the function must return $1$. Otherwise, it should return $0$. - Once the function returns $1$, your program will be terminated.

The sample grader reads the input in the following format: - Line $1$: $n\ m\ k$. - Line $2 + i$ ($0 \le i \le m - 1$): $u[i]\ v[i]$. The sample grader first calls `init`, and then calls `add_teleporter` in the order $i = 0, 1,\dots , m - 1$ with $u = u[i]$ and $v = v[i]$.

The program needs to print the index (from $0$ to $m - 1$, inclusive) of the first call to `add_teleporter` that returns $1$. If all calls to `add_teleporter` return $0$, your program should output $m$. If some call to `add_teleporter` returns an integer other than $0$ or $1$, the sample grader will print $-1$, and your program will be terminated immediately.

# Constraints - $1\le n\le 3\times 10^5$； - $1\le m\le 5\times 10^5$； - $1\le k\le n$。 For each call to the `add_teleporter` function: - $0\le u\le n-1$ and $0\le v\le n-1$； - Before teleporter $(u,v)$ is added, there is no teleporter from planet $u$ to planet $v$. # Subtasks 1. ($2$ points) $n=k$, $n\le 100$, $m\le 300$； 2. ($10$ points) $n\le 100$, $m\le 300$. 3. ($18$ points) $n\le 10^3$, $m\le 5\times 10^3$。 4. ($30$ points) $n\le 3\times 10^4$, $m\le 5\times 10^4$, $k\le 10^3$。 5. ($40$ points) No additional constraints. # Examples ## Example $1$ Consider the following function call: ```cpp init(6, 3) ``` In this example, there are $6$ planets and $3$ special planets. Planets numbered $0, 1, 2$ are special planets. The initial teleporters are $(0, 1)$ and $(1, 2)$. Suppose the grader performs the following calls: - (0) `add_teleporter(3, 4)`: should return $0$. - (1) `add_teleporter(5, 0)`: should return $0$. - (2) `add_teleporter(4, 5)`: should return $0$. - (3) `add_teleporter(5, 3)`: should return $0$. - (4) `add_teleporter(1, 4)`: in this case, it is possible to obtain infinitely many stamps. For example, the tourist can start from planet $0$ and travel in the order $1, 4, 5, 0, 1, 4, 5, 0,\dots$. Therefore, the function should return $1$, and then your program will be terminated. The figure below illustrates this example. Special planets and initial teleporters are shown in bold. Teleporters added via `add_teleporter` are labeled from $0$ to $4$ in the order they are added.  ## Example $2$ Consider the following function call: ```cpp init(4, 2) ``` In this example, there are $4$ planets and $2$ special planets. Planets numbered $0$ and $1$ are special planets. The initial teleporter is $(0, 1)$. Suppose the grader performs the following call: - `add_teleporter(1, 1)`: after adding teleporter $(1, 1)$, we can obtain infinitely many stamps. For example, a tourist can start from planet $1$ and use teleporter $(1, 1)$ to reach planet $1$ infinitely many times. Therefore, the function should return $1$, and then your program will be terminated. The attachment package also includes another sample input and output. Translated by ChatGPT 5