COCI '17 Contest 6 #2 Alkemija

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem types

In ancient times, when alchemists were searching for gold, the world was familiar with a total of $N$ $N$ distinct substances, denoted with $1$ $1$ to $N$ $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, \dots, X_L\}$ ${X_{1}, X_{2}, \dots, X_{L}}$ to another substance set $\{Y_1, Y_2, \dots, Y_R\}$ ${Y_{1}, Y_{2}, \dots, Y_{R}}$ . For example, the substance set $\{1, 4, 5\}$ ${1, 4, 5}$ might react once and create the new substance set $\{2, 6\}$ ${2, 6}$ .

Joško is a modern alchemist and has $M$ $M$ distinct substances denoted with $A_1, A_2, \dots, A_M$ $A_{1}, A_{2}, \dots, 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.

Input Specification

The first line of input contains two integers $N$ $N$ and $M$ $M$ $(1 \le M \le N \le 100\,000)$ $(1 \leq M \leq N \leq 100 000)$ , the numbers from the task.

The second line of input contains $M$ $M$ integers $A_i$ $A_{i}$ $(1 \le A_i \le N)$ $(1 \leq A_{i} \leq N)$ , labels of the substances Joško has in the beginning.

The third line of input contains the integer $K$ $K$ $(1 \le K \le 100\,000)$ $(1 \leq K \leq 100 000)$ , the number of known reactions.

The following $3K$ $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$ $L$ and $R$ $R$ $(1 \le L, R \le N)$ $(1 \leq L, R \leq N)$ .
The second line contains $L$ $L$ distinct integers $X_i$ $X_{i}$ $(1 \le X_i \le N)$ $(1 \leq X_{i} \leq N)$ .
The third line contains $R$ $R$ distinct integers $Y_i$ $Y_{i}$ $(1 \le Y_i \le N)$ $(1 \leq Y_{i} \leq N)$ .
This describes the reaction with which the substance set $\{X_1, X_2, \dots, X_L\}$ ${X_{1}, X_{2}, \dots, X_{L}}$ transforms into substance set $\{Y_1, Y_2, \dots, Y_R\}$ ${Y_{1}, Y_{2}, \dots, Y_{R}}$ .

The sum of all $L$ $L$ values won't exceed $100\,000$ $100 000$ .

The sum of all $R$ $R$ values won't exceed $100\,000$ $100 000$ .

Output Specification

The first line of output must contain the integer $X$ $X$ , the number of obtainable substances.

The second line of output must contain $X$ $X$ distinct integers $B_i$ $B_{i}$ , sorted ascendingly, that represent the labels of the obtainable substances.

Scoring

In test cases worth $60\%$ $60 %$ of total points, it will hold:

$N, K \le 500$ $N, K \leq 500$ .
The sum of all $L$ $L$ values and the sum of all $R$ $R$ values won't exceed $500$ $500$ .

Sample Input 1

Copy

Sample Output 1

Copy

4
1 2 3 4

Explanation for Sample Output 1

There are 2 reactions.

The first reaction transforms substance set $\{1, 2\}$ ${1, 2}$ into substance set $\{3\}$ ${3}$ .

The second reaction transforms substance set $\{1, 3\}$ ${1, 3}$ into substance set $\{4\}$ ${4}$ .

Joško initially has substances from the set $\{1, 2\}$ ${1, 2}$ .

Using the first reaction, Joško can obtain substance 3, after which he has substances from the set $\{1, 2, 3\}$ ${1, 2, 3}$ .

After that, using the second reaction, he can also obtain substance 4.

Sample Input 2

Copy

Sample Output 2

Copy

5
1 2 4 5 6

Explanation for Sample Output 2

Joško initially has substances from the set $\{1, 4, 5\}$ ${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.

Comments

0
MouradNouaili commented on Jan. 2, 2022, 8:42 p.m. ← edit 3 →
I don't see how the reactions are described in the input? sample #2

Copy
...... 1 3 4 1 5 6 1 1 6 2

How can I interpret this? Thx

0

Spitfire720 commented on Jan. 2, 2022, 10:21 p.m.

The first line you put(below the ...... line) represents L and R.

The next line after that contains L space-separated integers which would be the initial substance.

The line after would contain R space-separated integers which would be the result of the reaction of the initial substance.

You've copied two reactions from the sample input, so let's look at them both.

The first reaction basically tells us that one element, 4, will react to form three elements 1, 5, and 6.

The second reaction tells us that one element, 6, will react to form one element, 2.

Hope this helps :)

0

MouradNouaili commented on Jan. 9, 2022, 5:15 p.m. ← edited →

Thanks for replying, but I still confused about how the reactions are made?

0

Spitfire720 commented on Jan. 9, 2022, 7:48 p.m.

I see how you're interpreting it. The numbers you put in the reactions are actually still part of L, R, X, Y, etc.

Since K = 3, there are three known reactions, so the next 3K lines, or 9 lines, would describe those reactions. The six lines of which you are unsure of still deals with the reactions, which I explained in the earlier comment.

Hope this helps :)