题目描述
Stations (stations)
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₀, a₁, · · · , aₚ, such that a₀ = x, aₚ = 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 ≠ y). In this situation station z:
- executes a routing procedure that determines the neighbour of z which is on the unique path from z to y, and
- 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 first procedure is given n, the list of the links in the SIB and an integer k ≥ n − 1 as the inputs. It assigns each station a unique integer label between 0 and k, inclusive.
The second procedure is the routing procedure, which is deployed to all stations after labels are assigned. It is given only the following inputs:
* s, the label of the station that currently holds a packet,
* t, the label of the packet's target station (t ≠ s),
* c, the list of the labels of all neighbours of s.
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).
Implementation details
You should implement the following procedures:
int[] label(int n, int k, int[] u, int[] v)
- n: number of stations in the SIB.
- k: maximum label that can be used.
- u and v: arrays of size n − 1 describing the links. For each i (0 ≤ i ≤ n − 2), link i connects stations with indices u[i] and v[i].
- This procedure should return a single array L of size n. For each i (0 ≤ i ≤ n − 1) L[i] is the label assigned to station with index i. All elements of array L must be unique and between 0 and k, inclusive.
int find_next_station(int s, int t, int[] c)
- s: label of the station holding a packet.
- t: label of the packet's target station.
- c: an array giving the list of the labels of all neighbours of s. The array c is sorted in ascending order.
- This procedure should return the label of a neighbour of s that the packet should be forwarded to.
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,
* the returned labels are stored by the grading system, and
* 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.
Example
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.
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, the input comes from an arbitrarily chosen previous call to label. Consider the labels it produced. Then:
* $s$ and $t$ are labels of two different stations.
* $c$ is the sequence of all labels of neighbours of the station with label $s$, in ascending order.
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.
* $k = 10^9$
In this subtask you can obtain a partial score. Let $m$ be the maximum label value returned by label across all scenarios. Your score for this subtask is calculated according to the following table:
| Maximum label | Score |
|---|---|
| $m \ge 10^9$ | 0 |
| $2000 \le m < 10^9$ | $50 \cdot \log_{5000}(10^9/m)$ |
| $1000 < m < 2000$ | 50 |
| $m \le 1000$ | 61 |
Sample grader
The sample grader reads the input in the following format:
- line 1: r
r blocks follow, each describing a single scenario. The format of each block is as follows: - line 1: n k
- line 2 + i (0 ≤ i ≤ n − 2): u[i] v[i]
- line 1 + n: q: the number of calls to find_next_station.
- line 2 + n + j (0 ≤ j ≤ q − 1): z[j] y[j] w[j]: indices of stations involved in the j-th call to find_next_station. The station z[j] holds the packet, the station y[j] is the packet's target, and the station w[j] is the station that the packet should be forwarded to.
The sample grader prints the result in the following format:
- line 1: m
r blocks corresponding to the consecutive scenarios in the input follow. The format of each block is as follows: - line 1 + j (0 ≤ j ≤ q − 1): index of the station, whose label was returned by the j-th call to find_next_station in this scenario.
Note that each run of the sample grader calls both label and find_next_station.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp
<your code here>
Problem statement (Stations)
(stations)
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₀, a₁, · · · , aₚ, such that a₀ = x, aₚ = 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 ≠ y). In this situation station z:
- executes a routing procedure that determines the neighbour of z which is on the unique path from z to y, and
- 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 first procedure is given n, the list of the links in the SIB and an integer k ≥ n − 1 as the inputs. It assigns each station a unique integer label between 0 and k, inclusive.
The second procedure is the routing procedure, which is deployed to all stations after labels are assigned. It is given only the following inputs:
* s, the label of the station that currently holds a packet,
* t, the label of the packet's target station (t ≠ s),
* c, the list of the labels of all neighbours of s.
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).
Implementation details
You should implement the following procedures:
int[] label(int n, int k, int[] u, int[] v)
- n: number of stations in the SIB.
- k: maximum label that can be used.
- u and v: arrays of size n − 1 describing the links. For each i (0 ≤ i ≤ n − 2), link i connects stations with indices u[i] and v[i].
- This procedure should return a single array L of size n. For each i (0 ≤ i ≤ n − 1) L[i] is the label assigned to station with index i. All elements of array L must be unique and between 0 and k, inclusive.
int find_next_station(int s, int t, int[] c)
- s: label of the station holding a packet.
- t: label of the packet's target station.
- c: an array giving the list of the labels of all neighbours of s. The array c is sorted in ascending order.
- This procedure should return the label of a neighbour of s that the packet should be forwarded to.
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,
* the returned labels are stored by the grading system, and
* 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.
Example
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.
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, the input comes from an arbitrarily chosen previous call to label. Consider the labels it produced. Then:
* $s$ and $t$ are labels of two different stations.
* $c$ is the sequence of all labels of neighbours of the station with label $s$, in ascending order.
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.
* $k = 10^9$
In this subtask you can obtain a partial score. Let $m$ be the maximum label value returned by label across all scenarios. Your score for this subtask is calculated according to the following table:
| Maximum label | Score |
|---|---|
| $m \ge 10^9$ | 0 |
| $2000 \le m < 10^9$ | $50 \cdot \log_{5000}(10^9/m)$ |
| $1000 < m < 2000$ | 50 |
| $m \le 1000$ | 61 |
Sample grader
The sample grader reads the input in the following format:
- line 1: r
r blocks follow, each describing a single scenario. The format of each block is as follows: - line 1: n k
- line 2 + i (0 ≤ i ≤ n − 2): u[i] v[i]
- line 1 + n: q: the number of calls to find_next_station.
- line 2 + n + j (0 ≤ j ≤ q − 1): z[j] y[j] w[j]: indices of stations involved in the j-th call to find_next_station. The station z[j] holds the packet, the station y[j] is the packet's target, and the station w[j] is the station that the packet should be forwarded to.
The sample grader prints the result in the following format:
- line 1: m
r blocks corresponding to the consecutive scenarios in the input follow. The format of each block is as follows: - line 1 + j (0 ≤ j ≤ q − 1): index of the station, whose label was returned by the j-th call to find_next_station in this scenario.
Note that each run of the sample grader calls both label and find_next_station.
Execution limits
Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.
Starting code
Here's your starting code with some skeleton/placeholder functionality:
#include "stations.h"
#include <vector>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
return c[0];
}
参考代码
#include "stations.h"
#include <vector>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
return c[0];
}
请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。
输入格式
本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。
输出格式
由 manager 进程打印判定结果，无需自行写出答案。
样例输入
样例输出
提示
include "stations.h"
include <vector>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
return c[0];
}