A1367 | [COCI-2017_2018-contest6]#1 Alkemija
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
In ancient times, when alchemists were searching for gold, the world was familiar with a total of N distinct substances, denoted with 1 to N. During many years of hard work, searching for the secret formula, alchemists discovered a series of interesting regularities - alchemical reactions. In one reaction, it’s possible to transform substance set {X1, X2, …, XL} to another substance set {Y1, Y2, …, YR}. For example, the substance set {1, 4, 5} might react once and create the new substance set {2, 6}.
Joško is a modern alchemist and has M distinct substances denoted with A1, A2, …, AM. He has an unlimited quantity of each substance from that set. Joško wants to know which substances he can create using a list of reactions of ancient alchemists, so he’s asking you to help him solve this problem.
Joško is a modern alchemist and has M distinct substances denoted with A1, A2, …, AM. He has an unlimited quantity of each substance from that set. Joško wants to know which substances he can create using a list of reactions of ancient alchemists, so he’s asking you to help him solve this problem.
输入格式
The first line of input contains two integers N and M (1 ≤ M ≤ N ≤ 100 000), the numbers from the task.
The second line of input contains M integers Ai (1 ≤ Ai ≤ N), labels of the substances Joško has in the beginning.
The third line of input contains the integer K (1 ≤ K ≤ 100 000), the number of known reactions.
The following 3·K lines contain a list of reactions. Each reaction is described with 3 lines in the following way:
● The first line contains the integers L and R (1 ≤ L, R ≤ N).
● The second line contains L distinct integers Xi (1 ≤ Xi ≤ N).
● The third line contains R distinct integers Yi (1 ≤ Yi ≤ N).
● This describes the reaction with which the substance set {X1, X2, …, XL} transformsinto substance set {Y1, Y2, … YR}.
The sum of all L values won’t exceed 100 00
0.
The sum of all R values won’t exceed 100 00
0.
The second line of input contains M integers Ai (1 ≤ Ai ≤ N), labels of the substances Joško has in the beginning.
The third line of input contains the integer K (1 ≤ K ≤ 100 000), the number of known reactions.
The following 3·K lines contain a list of reactions. Each reaction is described with 3 lines in the following way:
● The first line contains the integers L and R (1 ≤ L, R ≤ N).
● The second line contains L distinct integers Xi (1 ≤ Xi ≤ N).
● The third line contains R distinct integers Yi (1 ≤ Yi ≤ N).
● This describes the reaction with which the substance set {X1, X2, …, XL} transformsinto substance set {Y1, Y2, … YR}.
The sum of all L values won’t exceed 100 00
0.
The sum of all R values won’t exceed 100 00
0.
输出格式
The first line of output must contain the integer X, the number of obtainable substances.
The second line of output must contain X distinct integers Bi , sorted ascendingly, that represent the labels of the obtainable substances.
The second line of output must contain X distinct integers Bi , sorted ascendingly, that represent the labels of the obtainable substances.
输入输出样例
输入 #1
4 2 1 2 2 2 1 1 2 3 2 1 1 3 4
输出 #1
4 1 2 3 4
输入 #2
6 3 1 4 5 3 3 2 2 3 4 1 6 1 3 4 1 5 6 1 1 6 2
输出 #2
5 1 2 4 5 6
In test cases worth 60% of total points, it will hold:
● N, K ≤ 500.
● The sum of all L values and the sum of all R values won’t exceed 500.
Clarification of the first test case:
There are 2 reactions.
The first reaction transforms substance set {1, 2} into substance set {3}.
The second reaction transforms substance set {1, 3} into substance set {4}.
Joško initially has substances from the set {1, 2}.
Using the first reaction, Joško can obtain substance 3, after which he has substances from the set {1,
2, 3}.
After that, using the second reaction, he can also obtain substance 4.
Clarification of the second test case:
Joško initially has substances from the set {1, 4, 5}.
Using the second reaction, it is possible to obtain substance 6, after which it is possible to apply the
third reaction, giving substance 2.
The first reaction is impossible to apply because Joško doesn’t have substance 3.
● N, K ≤ 500.
● The sum of all L values and the sum of all R values won’t exceed 500.
Clarification of the first test case:
There are 2 reactions.
The first reaction transforms substance set {1, 2} into substance set {3}.
The second reaction transforms substance set {1, 3} into substance set {4}.
Joško initially has substances from the set {1, 2}.
Using the first reaction, Joško can obtain substance 3, after which he has substances from the set {1,
2, 3}.
After that, using the second reaction, he can also obtain substance 4.
Clarification of the second test case:
Joško initially has substances from the set {1, 4, 5}.
Using the second reaction, it is possible to obtain substance 6, after which it is possible to apply the
third reaction, giving substance 2.
The first reaction is impossible to apply because Joško doesn’t have substance 3.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted