#P11711. 「KTSC 2020 R2」列车的移动
「KTSC 2020 R2」列车的移动
题目背景
请使用 C++17 或 C++20 提交本题
你需要在程序开头加入如下代码:
#include <vector>
void init(int N, std::vector<int> X, std::vector<int> Y);
long long train(std::vector<int> Z);
题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4「 열차의 이동」
题目描述
调车场是连接或分离列车车厢并进行维护和保养的地方。调车场中有可以移动列车的轨道。我们将用图来表示轨道上列车车厢的位置。图中的每条边表示列车的一个车厢所在的位置,因此列车在图中表示为一条路径。在这条路径上,所有的顶点和边都必须不同。特别地,问题中给出的图总是树形结构。
列车可以沿着轨道移动。列车的移动是分阶段进行的,每个阶段列车的一端车厢移动到相邻的另一条边上。具体来说,对于表示列车的路径 ,一次移动的结果是将 的一端顶点和相邻的 之外的边和顶点添加到 中,并将另一端的顶点和边从 中移除(见图 1)。注意,每个阶段路径的长度保持不变。
给定初始和最终列车位置的长度为 的路径 和 。路径的长度是路径中包含的边的数量。这里,路径 和 之间没有任何共享的边。换句话说, 和 没有同时经过的边。我们需要将路径 移动到最终成为路径 。此时,需要找到最少的移动步数。
给定包含 个顶点的树 以及初始和最终列车位置的长度为 的路径 和 ,编写一个程序,检查是否可以将 移动到 ,如果可以,输出最少的移动步数。
例如,在图 2 中,给定长度为 的两个路径 和 ,它们没有任何共享的边。可以看到,从路径 移动到路径 需要 步,这是最少的移动步数。
你需要为管理员实现以下两个函数:
void init(int n, vector<int> X, vector<int> Y);
- 该函数在程序开始时调用一次。树的顶点数量为 ,顶点编号从 到 。
X
和Y
是大小为 的vector
,表示树的每条边为 。
long long train(vector<int> Z);
- 参数
Z
是大小为 的vector
,表示初始路径 的两个端点Z[0]
和Z[1]
,以及最终路径 的两个端点Z[2]
和Z[3]
。函数返回将 移动到 的最少步骤数。如果无法移动,则返回-1
。
这些函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。
输入格式
评测程序按以下格式读取输入:
- 第 行:, 表示树的顶点数量,树的顶点编号从 到 , 表示查询的数量
- 接下来的 行:,表示树的一条边 ,
- 接下来的 行:,表示初始路径 的两个端点 和 ,最终路径 的两个端点 和
输出格式
评测程序将输出函数 train
的返回值。如果无法移动,则输出 -1
。
11 2
1 2
3 2
4 3
4 5
6 5
8 4
7 8
8 9
10 9
11 10
3 5 7 4
3 6 7 10
3
7
提示
样例说明 #1
以下是样例中函数调用及其结果的顺序:
函数调用 | 返回值 |
---|---|
init(11, {1,3,4,4,6,8,7,8,10,11}, {2,2,3,5,5,4,8,9,9,10}) |
|
train({3,5,7,4}) |
|
train({3,6,7,10}) |
数据范围
对于所有输入数据,满足:
- 所有查询中路径 的长度总和
详细子任务附加限制及分值如下表所示。
子任务 | 分值 | 约束 |
---|---|---|
路径 的长度 | ||
路径 的长度 ,所有路径 的长度总和 | ||
无附加限制 |
本题满分为 分。