XXII Open Cup. Grand Prix of Seoul |
---|
Finished |
The year 2021 marks the death of Adobe Flash, a multimedia software for animations, applications, games, and so on. Together with it, the era of Flash games (especially from 2005 to 2012) has started to fade away into history. Some good news on this front is that people have already been working on a way to preserve Flash content. Major efforts include Ruffle: an open source Flash player written in Rust, and Flashpoint: an archive of over 78,000 Flash applications.
In memory of the golden era of Flash games, we present a simplified variant of a famous Flash game called Factory Balls. You are tasked with painting a ball in a given pattern. The surface of a ball can be divided into $$$N$$$ distinct regions, enumerated with indices from 1 to $$$N$$$. You have $$$K$$$ paint cans full of paint, where the $$$i$$$-th paint can has the color $$$i$$$. You are also given $$$M$$$ pieces of equipment. Each piece of equipment is specified by a set of regions, and it precisely covers that subset of the regions of the ball.
In the beginning, all regions have color 1 and all pieces of equipment are unequipped. You may perform one of the following actions any number of times:
In the end, each region of the ball should have a specific color, and all pieces of equipment should be unequipped. Find the minimum number of actions required to paint the ball, or report that it is impossible.
The first line contains three integers: $$$N$$$, $$$K$$$, and $$$M$$$.
The next line contains $$$N$$$ integers. The $$$i$$$-th integer $$$c_i$$$ is the desired color of the $$$i$$$-th region.
Each of the next $$$M$$$ lines describes a piece of equipment. The first number of each line, $$$r_j$$$, denotes the number of regions the piece of equipment covers, followed by $$$r_j$$$ distinct positive integers, denoting the indices of the regions the piece of equipment covers.
If it's not possible to paint each region of the ball to a given color, output -1. Otherwise, output the minimum number of actions required.
3 5 3 1 3 5 1 1 1 2 1 3
6
4 3 2 3 3 2 1 2 1 2 2 2 3
7
4 2 2 1 2 2 1 2 1 2 2 3 4
-1
2 10 0 1 1
0
In the second example, this is the fastest method:
Name |
---|