P6838 [IOI 2020] Network Sites (Not Judgeable).

Singapore’s Internet backbone consists of $n$ network sites, which are assigned **indices** from $0$ to $n-1$. The Internet also has $n-1$ bidirectional links, numbered from $0$ to $n-2$. Each link connects two different sites. Two sites connected by a link are called neighbors of each other. A sequence of distinct sites $a_0,a_1,\ldots,a_p$ is called a path from site $x$ to site $y$ if and only if $a_0=x$, $a_p=y$, and every two consecutive sites in the sequence are neighbors. It is guaranteed that for any site $x$ and any other site $y$, there exists **exactly one** path. Any site $x$ can generate a packet and send it to any other site $y$, where site $y$ is called the packet’s **destination site**. The packet must be routed along the unique path from site $x$ to site $y$ according to the following rules. Suppose the packet has currently arrived at site $z$, where $y$ is the destination and $z \ne y$. Then site $z$ will: 1. Execute the **routing function** to find the neighbor of $z$ that lies on the unique path from $z$ to $y$. Then 2. Forward the packet to that neighbor. However, sites have limited storage memory and may not be able to store the full list of backbone links needed by the routing function. Your task is to implement the routing mechanism of the backbone, which consists of two functions. - The first function takes as input $n$, the list of backbone links, and an integer $k \ge n-1$. This function must assign each site a unique **label**, with values between $0$ and $k$ (inclusive). - The second function is the routing function. After the labels are assigned, it is deployed on all sites. Its input parameters are: - $s$, the **label** of the site where the packet is currently located, - $t$, the **label** of the destination site $(t \ne s)$, - $c$, the list of **labels** of all neighboring sites of $s$. This function should return the **label** of a neighbor of $s$, indicating the next site to which the packet should be forwarded. In each subtask, your score depends on the maximum label assigned among all sites (in general, the smaller the maximum label, the better). #### Implementation Details You need to implement the following functions: ```cpp int[] label(int n, int k, int[] u, int[] v) ``` - $n$: the number of sites in the backbone. - $k$: the maximum available label value. - $u$ and $v$: arrays of size $n-1$ describing the links. For each $i(0 \le i \le n-2)$, link $i$ connects the sites with indices $u[i]$ and $v[i]$. - This function should return an array $L$ of size $n$. For each $i(0 \le i \le n-1)$, $L[i]$ is the label assigned to the site with index $i$. All elements of $L$ must be pairwise distinct and between $0$ and $k$ (inclusive). ```cpp int find_next_station(int s, int t, int[] c) ``` - $s$: the label of the site where the packet is currently located. - $t$: the label of the destination site. - $c$: an array containing the labels of all neighbors of $s$. The array $c$ is sorted in increasing order. - This function should return the label of a neighbor of $s$, indicating the next site to which the packet should be forwarded. Each test case contains one or more independent scenarios (i.e., different backbone descriptions). For a test case containing $r$ scenarios, the grader will run the above functions exactly twice, following the steps below. During the first run: - The `label` function is called $r$ times. - The returned labels are saved by the grading system. - `find_next_station` is not called. During the second run: - `find_next_station` is called multiple times. For each call, the grader chooses an arbitrary scenario, and the labeling returned by the `label` function for that scenario is used for this `find_next_station` call. - `label` is not called. - In particular, any information stored in static or global variables during the first run of the grader cannot be used in the `find_next_station` function. #

#

#

#### Sample Explanation #### Example 1 Consider the following call: ```cpp label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4]) ``` There are $5$ sites and $4$ links. The pairs of site indices for the links are $(0,1)$, $(1,2)$, $(1,3)$, and $(2,4)$. The labels range from $0$ to $k=10$. To return the following labeling scheme: |Index|Label| |:-:|:-:| |$0$| $6$| |$1$| $2$| |$2$|$9$| |$3$ |$3$| |$4$ |$7$| the function `label` should return $[6,2,9,3,7]$. The numbers in the figure below show the site indices (left) and the assigned labels (right).  Assume the labels are assigned as shown above, and consider the following call: ```cpp find_next_station(9, 6, [2, 7]) ``` This means the packet is currently at the site with label $9$, and its destination site has label $6$. Along the path from the current site to the destination site, the site labels are $[9,2,6]$. Therefore, the function should return $2$, indicating that the packet should be forwarded to the site with label $2$ (whose index is $1$). Consider another possible call: ```cpp find_next_station(2, 3, [3, 6, 9]) ``` This function should return $3$, because the destination site (label $3$) is a neighbor of the current site (label $2$), so the destination site directly receives the packet. #### Constraints - $1 \le r \le 10$ For each call to `label`: - $2 \le n \le 1000$ - $k \ge n-1$ - $0 \le u[i],v[i] \le n-1$（for all $0 \le i \le n-2$） For each call to `find_next_station`, its input parameters come from labels produced by some previously chosen call to `label`. With respect to the produced labels: - $s$ and $t$ are the labels of two different sites. - $c$ is the sequence of labels of all neighbors of the site with label $s$, sorted in increasing order. For each test case, across all scenarios combined, the total length of all arrays $c$ passed to the function `find_next_station` does not exceed $10^5$. #### Subtasks 1. (5 points) $k=1000$, no site will have more than $2$ neighbors. 2. (8 points) $k=1000$, link $i$ connects sites $i+1$ and $\lfloor\frac{i}{2}\rfloor$. 3. (16 points) $k=10^6$, at most one site has more than $2$ neighbors. 4. (10 points) $n \le 8$, $k = 10^9$ 5. (61 points) $k = 10^9$ In subtask 5, you can receive partial credit. Let $m$ be the maximum label returned by `label` across all scenarios. For this subtask, your score is computed according to the table below: |Maximum label|Score| |:-:|:-:| |$m \ge 10^9$|$0$| |$2000 \le m < 10^9$|$50 \cdot \log_{5 \cdot10^5}(\frac{10^9}{m})$| |$1000 < m < 5000$|$50$| |$m \le 1000$|$61$| #### Sample Grader The sample grader reads the input data in the following format: Line $1$: $r$ Then follow $r$ blocks, each describing one scenario, in the following format: Line $1$: $n\ k$ Lines $2+i(0 \le i \le n-2)$: $u[i]\ v[i]$ Line $1+n$: $q$, the number of calls to `find_next_station` Lines $2+n+j(0 \le j \le q-1)$: $z[j]\ y[j]\ w[j]$, the **indices** of the sites involved in the $j$-th call to `find_next_station`. At this time, the packet is at site $z[j]$, the destination site is $y[j]$, and it should be forwarded to site $w[j]$. The sample grader prints your output in the following format: Line $1$: $m$ Then follow $r$ blocks corresponding to the scenarios in the input. Each block has the following format: Lines $1+j(0 \le j \le q-1)$: a site **index**, whose corresponding **label** is the result returned by the $j$-th call to `find_next_station`. Note: each time the sample grader is executed, it calls both `label` and `find_next_station`. Translated by ChatGPT 5