## Wesley's Anger Contest 4 Problem 5 - Time Travelling Squirrels

View as PDF

Points: 30 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types

The squirrel nation is building a road network to transport acorns between their cities. They are scattered among different cities, the of which currently has acorns. Initially, in the original timeline, the cities are disconnected from each other.

Over time, different squirrels will perform one of three types of actions:

1. A squirrel will build more roads to connect some of their cities. Of course, the squirrels, having recently discovered time travel, will sometimes go back in time and build the roads a different way. Specifically, the squirrel will decide to time travel to the same timeline as another squirrel , where , and build a new road in that timeline between cities and .
2. A squirrel will time travel back to the same timeline as another squirrel , where , start in a specific city , and eat all the acorns in the city with the largest number of acorns that is reachable from city (including city ). If there are multiple cities with the largest number of acorns, then the squirrel will pick one arbitrarily.
3. A squirrel will time travel back to the same timeline as another squirrel , where , start in a specific city , and add acorns to each city reachable from city (including city ).

Note that each squirrel creates a new timeline, so future actions cannot affect past actions. When a squirrel time travels to the same timeline as another squirrel , all actions performed by squirrel have already occurred.

You are asked to record the number of acorns eaten after each type action. Can you help the squirrel nation keep track of all the acorns eaten?

#### Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

for all
for all
for all
for all

for all
There will be no actions of type .

for all

There will be no actions of type .

#### Input Specification

The first line of input contains integers, and , representing the number of cities in the squirrel nation, and the number of time travelling squirrels.

The next line contains integers, which describe the initial number of the acorns in each city. The integer on this line is , indicating that the city initially has acorns.

The next lines describe the squirrels' actions. The input will be given in encrypted format. Instead of each variable being given, a variable will be given instead. To decrypt the input, you should take the bitwise of the last value that was outputted, and , that is . If no previous value was outputted, then . Note that the first integer on each line providing the type of action is not encrypted.

The of these lines will be in one of three forms.

• 1 j_i' a_i' b_i' indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and building a new road between cities and .
• 2 j_i' a_i' indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and eating all acorns from the city with the largest number of acorns that is reachable from city (including city ). If there are multiple cities with the largest number of acorns, the squirrel will pick one arbitrarily.
• 3 j_i' a_i' c_i' indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and adding acorns to each city reachable from city (including city ).

For all squirrels, if , then squirrel has time travelled back to the original timeline, where all cities are disconnected.

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

After each type action, output the number of acorns eaten by that squirrel. If no acorns were eaten by that squirrel, output instead.

#### Sample Input 1

2 3
1 2
2 0 2
1 3 3 0
2 0 0

#### Sample Input 1 Decrypted

For your convenience, below is a version of Sample Input 1 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.

2 3
1 2
2 0 2
1 1 1 2
2 2 2

#### Sample Output 1

2
1

#### Sample Explanation 1

Squirrel time travels to the original timeline, starts in city , and eats acorns from city .
Squirrel time travels to squirrel 's timeline and builds a road between cities and .
Squirrel time travels to squirrel 's timeline, starts in city , and eats acorn from city . Note that they cannot eat any acorns from city since they were already eaten by squirrel , and this timeline was created from squirrel 's timeline, which in turn was created form squirrel 's timeline.

#### Sample Input 2

3 7
1 2 1
1 0 1 2
2 1 2
3 2 1 0
1 1 0 1
2 6 0
2 3 1
2 4 0

#### Sample Input 2 Decrypted

For your convenience, below is a version of Sample Input 2 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.

3 7
1 2 1
1 0 1 2
2 1 2
3 0 3 2
1 3 2 3
2 4 2
2 0 2
2 6 2

#### Sample Output 2

2
3
2
0

#### Sample Explanation 2

Squirrel time travels to the original timeline and builds a road between cities and .
Squirrel time travels to squirrel 's timeline, starts in city , and eats acorns from city
Squirrel time travels to the original timeline and adds acorns to all cities reachable from city (which is just city ).
Squirrel time travels to squirrel 's timeline and builds a road between cities and .
Squirrel time travels to squirrel 's timeline, starts in city , and eats the acorns from city .
Squirrel time travels to the original timeline, starts in city , and eats acorns from city .
Squirrel time travels to squirrel 's timeline, starts in city , and does not eat any acorns, as they are no cities reachable from city that have acorns in this timeline.