| IME++ Open Contest 2024 |
|---|
| Finished |
A lovely couple, Sergio and Ana, go out on a romantic evening to paint. They go to this place that has some very special paint colors, which are able to glow in the dark and some of which have some very funky effects! The event starts with the couple receiving $$$q$$$ blank canvases, and a whole variety of $$$k$$$ colors to choose from. The colors are numbered from $$$1$$$ to $$$k$$$. These can be divided into two: those who are weird and those who are permanent. The colors that are deemed weird have this special effect: if a person tries to color the canvas an even amount of times with the same weird color, every speck of it magically disappears! Permanent colors don't suffer from this (un)fortunate condition.
This painting gallery has some very strict rules on how to use the colors: the couple has $$$n$$$ color palettes to choose from, and once the palettes are chosen, they need to use every color contained in each one. As per guidelines, permanent colors can't be present in the same palette as weird ones. These palettes each contain each color at most once, and contains enough paint of each color to paint the entire canvas (the couple doesn't need to use the same palette twice). Every canvas is an independent query, so they have the complete set of palettes available.
For each $$$q_i$$$ canvas, Ana decides that she wants Sergio to paint it using a specific array of colors. As Sergio wants to paint each one without tiring himself too much, he wants to know for each canvas, what's the least amount of different palettes that he has to choose from in order to satisfy Ana.
The first line contains three integers, $$$n$$$, $$$k$$$, $$$q$$$, $$$(1 \leq n \leq 2 \times 10^5)$$$, $$$(1 \leq k \leq 20)$$$, $$$(1 \leq q \leq 10^6)$$$ — the number of palettes, the number of distinct colors and the number of canvases.
The second line will contain a string $$$s$$$, $$$|s| = k$$$, containing only the letters W and P, indicating whether the $$$i^{th}$$$ color is weird or permanent.
The next $$$n$$$ lines will describe the color palettes that exist. Each line begins with an integer $$$m$$$, $$$(1 \leq m \leq k)$$$ indicating the amount of colors that are contained in this palette. In the next $$$m$$$ integers on the same line, $$$(1 \leq c_1, c_2, ..., c_m \leq k)$$$ — the colors in the palette. It is guaranteed that every color in the same palette is of the same type.
The next $$$q$$$ lines will describe the colors in the canvases that Ana desires. Each line begins with an integer $$$t$$$, $$$(1 \leq t \leq k)$$$, indicating the amount of colors that Ana desires in her canvas. In the next $$$t$$$ integers on the same line, $$$(1 \leq a_1, a_2, ..., a_t \leq k)$$$ — the colors that are desired.
For each query, print out the minimum amount of palettes needed in order to get the colors that Ana desires. If it's not possible, print $$$-1$$$.
3 5 2WPWWP2 1 32 2 53 1 3 45 1 2 3 4 51 1
2 -1
5 7 4WWPPWPW3 2 5 73 1 7 52 3 41 62 2 55 1 7 2 3 44 1 2 3 42 4 63 5 6 2
3 3 -1 2
In the first example:
For the first canvas, Sergio is able to color it using the second and third palettes. It is easy to see that for the second canvas, it is impossible to reach the color array desired.
In the second example:
The second canvas can be created using palettes 1, 2, 3. The fourth canvas can be created using palettes 4 and 5.
| Name |
|---|


