Alkemija
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 80\) points
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 { \(X\) {1}{ }, \(X\) {2}{ }, ..., \(X\) {L}{ }} to another
substance set { \(Y\) {1}{ }, \(Y\) {2}{ }, ..., \(Y\) {R}{ }}. 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 \(A\) {1}{ }, \(A\) {2}{ }, ..., \(A\) {M}{ }. 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.
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.
1 \(s / 64\) \(MB / 80\) points
The first line of input contains two integers \(N\) and \(M\) (1 ≤ \(M\) ≤ \(N \le 100\,000\)), the numbers
from the task.
The second line of input contains \(M\) integers \(A\) {i} (1 ≤ \(A\) ≤ \(N\) ), labels of the substances Joško
has in the beginning.
The third line of input contains the integer \(K\) (1 ≤ \(K \le 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 \(X\) {i}{ } (1 ≤ \(X\) {i}{ } ≤ \(N\) ).
●
The third line contains \(R\) distinct integers \(Y\) {i}{ } (1 ≤ \(Y\) {i}{ } ≤ \(N\) ).
●
This describes the reaction with which the substance set { \(X\) {1}{ }, \(X\) {2}{ }, ..., \(X\) {L}{ }} transforms
into substance set { \(Y\) {1}{ }, \(Y\) {2}{ }, ..., \(Y\) {R}{ }}.
The sum of all \(L\) values won’t exceed 100 000.
The sum of all \(R\) values won’t exceed 100 000.
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 \(B\) {i}{ }, sorted ascendingly, that
represent the labels of the obtainable substances.
4 2
1 2
2
2 1
1 2
3
2 1
1 3
4
6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2output
4
1 2 3 4
5
1 2 4 5 6Clarification 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.
평가 및 의견
Alkemija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Alkemija