IOI '19 P2 - Split the Attractions

View as PDF

Points: 40 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
C++

There are attractions in Baku, numbered from to . There are also two-way roads, numbered from to . Each road connects two different attractions. It is possible to travel between any pair of attractions through the roads.

Fatima is planning to visit all of the attractions in three days. She already decided that she wants to visit attractions on the first day, attractions on the second day, and attractions on the third day. Therefore, she is going to partition the attractions into three sets and of sizes and respectively. Each attraction will belong to exactly one set, so .

Fatima would like to find the sets and so that at least two out of the three sets are connected. A set of attractions is called connected if it is possible to travel between any pair of attractions in by using the roads and without passing through any attraction not in . A partition of attractions into sets and is called valid if it satisfies the conditions described above.

Help Fatima find a valid partition of the attractions (given , , and ), or determine that no valid partition exists. If there are multiple valid partitions, you may find any of them.

Implementation details

You should implement the following procedure:

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int>p, std::vector<int>q)

• : the number of attractions.
• and : the desired sizes of sets and .
• and : arrays of length , containing the endpoints of the roads. For each , and are the two attractions connected by road .
• This procedure should return an array of length . Denote the array by . If there is no valid partition, should contain zeros. Otherwise, for should be one of or to denote that attraction is assigned to set or respectively.

Examples

Example 1

Consider the following call:

find_split(9, 4, 2, 3, [0, 0, 0, 0, 0, 0, 1, 3, 4, 5], [1, 2, 3, 4, 6, 8, 7, 7, 5, 6])


A possible correct solution is . This solution describes the following partition: and . The sets and are connected.

Example 2

Consider the following call:

find_split(6, 2, 2, 2, [0, 0, 0, 0, 0], [1, 2, 3, 4, 5])


No valid partition exists. Therefore, the only correct answer is .

Constraints

• There is at most one road between each pair of attractions.
• It is possible to travel between any pair of attractions through the roads.
• and for

1. ( points) Each attraction is an endpoint of at most two roads.
2. ( points)
3. ( points)
4. ( points)
5. ( points) No additional constraints.

The sample grader prints a single line containing the array returned by find_split.