Prefix Enlightenment
Contest: Codeforces Round 616 (Div. 1)
Difficulty rating: 2400
Tags: dfs and similar, dsu, graphs

There are $$$n$$$ lamps on a line, numbered from $$$1$$$ to $$$n$$$. Each one has an initial state off ($$$0$$$) or on ($$$1$$$).

You're given $$$k$$$ subsets $$$A_1, \ldots, A_k$$$ of $$$\{1, 2, \dots, n\}$$$, such that the intersection of any three subsets is empty. In other words, for all $$$1 \le i_1 < i_2 < i_3 \le k$$$, $$$A_{i_1} \cap A_{i_2} \cap A_{i_3} = \varnothing$$$.

In one operation, you can choose one of these $$$k$$$ subsets and switch the state of all lamps in it. It is guaranteed that, with the given subsets, it's possible to make all lamps be simultaneously on using this type of operation.

Let $$$m_i$$$ be the minimum number of operations you have to do in order to make the $$$i$$$ first lamps be simultaneously on. Note that there is no condition upon the state of other lamps (between $$$i+1$$$ and $$$n$$$), they can be either off or on.

You have to compute $$$m_i$$$ for all $$$1 \le i \le n$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$).

The second line contains a binary string of length $$$n$$$, representing the initial state of each lamp (the lamp $$$i$$$ is off if $$$s_i = 0$$$, on if $$$s_i = 1$$$).

The description of each one of the $$$k$$$ subsets follows, in the following format:

The first line of the description contains a single integer $$$c$$$ ($$$1 \le c \le n$$$)  — the number of elements in the subset.

The second line of the description contains $$$c$$$ distinct integers $$$x_1, \ldots, x_c$$$ ($$$1 \le x_i \le n$$$)  — the elements of the subset.

It is guaranteed that:

- The intersection of any three subsets is empty;
- It's possible to make all lamps be simultaneously on using some operations.

Output format:
You must output $$$n$$$ lines. The $$$i$$$-th line should contain a single integer $$$m_i$$$  — the minimum number of operations required to make the lamps $$$1$$$ to $$$i$$$ be simultaneously on.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example:

- For $$$i = 1$$$, we can just apply one operation on $$$A_1$$$, the final states will be $$$1010110$$$;
- For $$$i = 2$$$, we can apply operations on $$$A_1$$$ and $$$A_3$$$, the final states will be $$$1100110$$$;
- For $$$i \ge 3$$$, we can apply operations on $$$A_1$$$, $$$A_2$$$ and $$$A_3$$$, the final states will be $$$1111111$$$.

In the second example:

- For $$$i \le 6$$$, we can just apply one operation on $$$A_2$$$, the final states will be $$$11111101$$$;
- For $$$i \ge 7$$$, we can apply operations on $$$A_1, A_3, A_4, A_6$$$, the final states will be $$$11111111$$$.

Example input:
7 3
0011100
3
1 4 6
3
3 4 7
2
2 3

Example output:
1
2
3
3
3
3
3

Example input:
8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2

Example output:
1
1
1
1
1
1
4
4

Editorial:
The condition "the intersection of any three subsets is empty" can be easily rephrased in a more useful way: each element appears in at most two subsets.
Let's suppose for the moment that each elements appears in exactly two subsets. We can think of each element as an edge between the subsets, it's a classical point of view. If we see subsets as nodes, we can model the subsets choice by coloring nodes into two colors, "taken" or "non-taken".
If an element is initially off, we need to take exactly one of the subsets containing it. The corresponding edge should have endpoints with different color. If an element is initially on, we must take none or both subsets : endpoints with same color.
We recognize a sort of bipartition, obviously there are at most two correct colorings for each connected component: fixing the color of a node fix the color of all connected nodes.
Hence, the final answer is the sum for each component, of the size of the smaller side of the partition.
Since the answer exists for $$$i = n$$$, there exists a such partition of the graph (into "red" and "blue" nodes). We can find it with usual dfs, and keep it for lower values of $$$i$$$.
In order to compute all $$$m_i$$$ efficiently, we start from a graph with no edges ($$$i = 0$$$), and we add edges with DSU, maintaining in each connected component the count of nodes in red side, and the count of nodes in blue side.
Now, how to deal with elements that appears in exactly one subset? They don't add any edge in the graph, but they force to take one of the sides of the connected component. To simulate this, we can use a special forced flag, or just fix the count of the other side to $$$+\infty$$$ (but be careful about overflow if you do that).
Final complexity : $$$O((n+k) \cdot \alpha(k))$$$.