MWC '15 #6 P3: Magical Sets

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 0.3s

Memory limit: 64M

Author:

aurpine

Problem types

A mathematical set is a collection of distinct elements (integers). When you merge two sets, all the elements in each set are in the new set. Since each element is distinct, duplicate elements are turned into a single element.

A magical set is like a mathematical set, but with a magical merge. Instead of combining duplicate elements into a single element, a magical set, when merged, gets rid of both duplicates.

For example, sets $A: \{1, 5, 6, 10\}$ $A : {1, 5, 6, 10}$ and $B: \{2, 5, 6\}$ $B : {2, 5, 6}$ , when merged become $\{1, 2, 5, 6, 10\}$ ${1, 2, 5, 6, 10}$ . If the two sets were magical sets, the resulting merged magical set is $\{1, 2, 10\}$ ${1, 2, 10}$ . However, this only applies to merging of two magical sets. The magical merge is a commutative operation. To merge three sets, you would first merge two of them, then merge the third with the result of the first merge. Note: sets are not necessarily given in sorted order. It is guaranteed that no duplicates are given.

Create a program to simulate the merging of a number of magical sets. You may have to merge more than 2 magical sets together.

Input Specification

The first line contains two integers, $N$ $N$ $(1 \le N \le 1000)$ $(1 \leq N \leq 1000)$ , the number of magical sets and $Q$ $Q$ $(1 \le Q \le 1000)$ $(1 \leq Q \leq 1000)$ , the number of magical set merge queries to perform.

The next $N$ $N$ lines start with integer $S_n$ $S_{n}$ $(0 \le S_n \le 61)$ $(0 \leq S_{n} \leq 61)$ , the size of the respective magical set (numbered $1$ $1$ to $N$ $N$ ), followed by $S_n$ $S_{n}$ integers in the magical set $i_s$ $i_{s}$ $(-30 \le i_s \le 30)$ $(- 30 \leq i_{s} \leq 30)$ .

The next $Q$ $Q$ lines start with an integer $M$ $M$ $(0 \le M \le N)$ $(0 \leq M \leq N)$ , the number of magical sets to merge. $M$ $M$ integers follow, the ids of the sets to merge together.

Note: you will have to use fast input methods.

Constraints

Subtask 1 [5%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$1 \le Q \le 100$ $1 \leq Q \leq 100$

Subtask 2 [5%]

$1 \le N \le 1000$ $1 \leq N \leq 1000$

$1 \le Q \le 100$ $1 \leq Q \leq 100$

Subtask 3 [90%]

$1 \le N \le 1000$ $1 \leq N \leq 1000$

$1 \le Q \le 1000$ $1 \leq Q \leq 1000$

Output Specification

$Q$ $Q$ lines, each containing the size followed by the elements in each resulting magical set in ascending order.

Sample Input

Copy

Sample Output

Copy

3 1 2 10
3 2 5 6
6 1 2 3 4 7 10

Explanation for Sample Output

The first merge was explained above. Only one set participates in the second merge query, so the result is identical to the second magical set. All three magical sets are merged. Since the merge is commutative, we can merge the third set with the result of the first merge to get $\{1, 2, 3, 4, 7, 10\}$ ${1, 2, 3, 4, 7, 10}$ .

Comments

1

richardyi25 commented on May 1, 2016, 2:03 a.m.

What do we output if the merged magical set is empty?

4
aurpine commented on May 1, 2016, 2:07 p.m.
r3mark is correct. It still follows the same format: size, followed by (no) elements.

Copy
0

4

r3mark commented on May 1, 2016, 2:11 a.m.

Just "0" I think.