#P17804. [ICPC 2019 Nanchang R] 9102
[ICPC 2019 Nanchang R] 9102
题目描述
众所周知,存在着无数代表不同世界的“世界线”。任何微小的改变都可能创造出一条新的世界线。
现在是公元 9102 年,人类已经在火星上生活了数千年,形成了许多部落。每个部落包含一个或多个家族。两个部落可以进行合并,其中一个部落中的所有家族都会迁往另一个部落;一个家族可能会灭绝,或者从其原来的部落迁徙到另一个家族所在的部落。
作为造物主,你统治着整个宇宙,因此你对火星上的一切都了如指掌。由于你经常忘记事情,你决定编写一个程序来管理这些正在发生的事情。
假设火星上有 个部落,最初每个部落仅由一个家族构成。我们将这些部落以及这些家族从 到 进行编号。你的程序需要支持以下五种类型的操作:
1 k a b:将包含第 个家族的部落与包含第 个家族的部落合并;2 k a:使第 个家族灭绝;3 k a b:第 个家族离开其所在部落,加入包含第 个家族的部落;4 k a b:报告第 个家族与第 个家族是否属于同一个部落;5 k a:报告包含第 个家族的部落中的家族总数。
注意,对于每个带有参数 的给定操作,你需要将自身置于第 个操作之后的时间点的世界线中。
当你处理类型为 1 或 3 的操作时,第 个家族与第 个家族可能已经位于同一部落中,此时不会发生任何事情。同样地,给定的数字 或 可能指向一个已灭绝的家族,此时对于前三种类型的操作,不会发生任何事情;对于第四种类型的操作,应报告 No;对于第五种操作,应报告 0。
输入格式
第一行包含两个整数 和 (),分别表示初始的家族数量与操作数量。
接下来的 行包含五种操作。第 行包含三个或四个整数 , , 和 (, , )。
输出格式
对于操作 4,你需要输出一行 Yes 或 No(不含引号);对于操作 5,你需要输出一行包含一个整数。
4 6
1 0 1 2
1 0 4 2
3 2 4 3
5 3 3
2 1 1
4 5 3 4
2
No
提示
:::align{center}
:::
翻译由 DeepSeek V4 Pro 完成