시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 | 1024 MB | 204 | 68 | 67 | 42.949% |
Singapore's Internet Backbone (SIB) consists of $n$ stations, which are assigned indices from $0$ to $n-1$. There are also $n-1$ bidirectional links, numbered from $0$ to $n-2$. Each link connects two distinct stations. Two stations connected with a single link are called neighbours.
A path from station $x$ to station $y$ is a sequence of distinct stations $a_0,a_1,\cdots,a_p$, such that $a_0=x$, $a_p=y$, and every two consecutive stations in the path are neighbours. There is exactly one path from any station $x$ to any other station $y$.
Any station $x$ can create a packet (a piece of data) and send it to any other station $y$, which is called the packet's target. This packet must be routed along the unique path from $x$ to $y$ as follows. Consider a station $z$ that currently holds a packet, whose target station is $y$ ($z \neq y$). In this situation station $z$: 1. executes a routing procedure that determines the neighbour of $z$ which is on the unique path from $z$ to $y$, and 2. forwards the packet to this neighbour.
However, stations have limited memory and do not store the entire list of the links in SIB to use it in the routing procedure.
Your task is to implement a routing scheme for SIB, which consists of two procedures.
The second procedure is the routing procedure, which is deployed to all stations after labels are assigned. It is given only the following inputs:
It should return the label of the neighbour of $s$ that the packet should be forwarded to.
In one subtask, the score of your solution depends on the value of the maximum label assigned to any station (in general, smaller is better).
You should implement the following procedures:
int[] label(int n, int k, int[] u, int[] v)
int find_next_station(int s, int t, int[] c)
Each test case involves one or more independent scenarios (i.e., different SIB descriptions). For a test case involving $r$ scenarios, a program that calls the above procedures is run exactly two times, as follows.
During the first run of the program:
label
procedure is called $r$ times,find_next_station
is not called.During the second run of the program:
find_next_station
may be called multiple times. In each call, an arbitrary scenario is chosen, and the labels returned by the call to label
procedure in that scenario are used as the inputs to find_next_station
.label
is not called.In particular, any information saved to static or global variables in the first run of the program is not available within find_next_station
procedure.
For each call to label
:
For each call to find_next_station
, the input comes from an arbitrarily chosen previous call to label
. Consider the labels it produced. Then:
For each test case, the total length of all arrays $c$ passed to the procedure find_next_station
does not exceed $100\;000$ for all scenarios combined.
Consider the following call:
label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4])
There are a total of $5$ stations, and $4$ links connecting pairs of stations with indices $(0, 1)$, $(1, 2)$, $(1, 3)$ and $(2, 4)$. Each label can be an integer from $0$ to $k=10$.
In order to report the following labelling:
Index | Label |
---|---|
0 | 6 |
1 | 2 |
2 | 9 |
3 | 3 |
4 | 7 |
the label
procedure should return [$6$, $2$, $9$, $3$, $7$]. The numbers in the following figure show the indices (left panel) and assigned labels (right panel).
Assume the labels have been assigned as described above and consider the following call:
find_next_station(9, 6, [2, 7])
This means that the station holding the packet has label $9$, and the target station has label $6$. The labels of stations on the path to the target station are $[9, 2, 6]$. Hence, the call should return $2$, which is the label of the station that the packet should be forwarded to (which has index $1$).
Consider another possible call:
find_next_station(2, 3, [3, 6, 9])
The procedure should return $3$, since the target station with label $3$ is a neighbour of the station with label $2$, and hence should receive the packet directly.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $k = 1000$, no station has more than $2$ neighbours. |
2 | 8 | $k = 1000$, link $i$ connects stations $i+1$ and $\left\lfloor \frac{i}{2} \right\rfloor$. |
3 | 16 | $k = 1\;000\;000$, at most one station has more than $2$ neighbours. |
4 | 10 | $n \leq 8$, $k = 10^9$ |
5 | 61 | $k = 10^9$ |
Olympiad > International Olympiad in Informatics > IOI 2020 > Day 2 6번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)