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

View as PDF

Submit solution


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 N different cities, the k^{th} of which currently has z_k acorns. Initially, in the original timeline, the cities are disconnected from each other.

Over time, Q 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 i^{th} squirrel will decide to time travel to the same timeline as another squirrel j_i, where j_i < i, and build a new road in that timeline between cities a_i and b_i.
  2. A squirrel will time travel back to the same timeline as another squirrel j_i, where j_i < i, start in a specific city a_i, and eat all the acorns in the city with the largest number of acorns that is reachable from city a_i (including city a_i). 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 j_i, where j_i < i, start in a specific city a_i, and add c_i acorns to each city reachable from city a_i (including city a_i).

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

You are asked to record the number of acorns eaten after each type 2 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 subtasks:

1 \le N, Q \le 100\,000
1 \le z_k \le 10^9 for all 1 \le k \le N
0 \le j_i < i for all 1 \le i \le Q
1 \le a_i, b_i \le N for all 1 \le i \le Q
1 \le c_i \le 10^9 for all 1 \le i \le Q

Subtask 1 [13%]

1 \le N, Q \le 2\,000

Subtask 2 [14%]

j_i = i-1 for all 1 \le i \le Q
There will be no actions of type 3.

Subtask 3 [20%]

j_i = i-1 for all 1 \le i \le Q

Subtask 4 [20%]

There will be no actions of type 3.

Subtask 5 [33%]

No additional constraints.

Input Specification

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

The next line contains N integers, which describe the initial number of the acorns in each city. The k^{th} integer on this line is z_k, indicating that the k^{th} city initially has z_k acorns.

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

The i^{th} of these lines will be in one of three forms.

  • 1 j_i' a_i' b_i' indicating that squirrel i performs a type 1 action by time traveling back to the same timeline as squirrel j_i, creating a new timeline, and building a new road between cities a_i and b_i.
  • 2 j_i' a_i' indicating that squirrel i performs a type 2 action by time traveling back to the same timeline as squirrel j_i, creating a new timeline, and eating all acorns from the city with the largest number of acorns that is reachable from city a_i (including city a_i). 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 i performs a type 3 action by time traveling back to the same timeline as squirrel j_i, creating a new timeline, and adding c_i acorns to each city reachable from city a_i (including city a_i).

For all squirrels, if j_i = 0, then squirrel i 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 2 action, output the number of acorns eaten by that squirrel. If no acorns were eaten by that squirrel, output 0 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 1 time travels to the original timeline, starts in city 2, and eats 2 acorns from city 2.
Squirrel 2 time travels to squirrel 1's timeline and builds a road between cities 1 and 2.
Squirrel 3 time travels to squirrel 2's timeline, starts in city 2, and eats 1 acorn from city 1. Note that they cannot eat any acorns from city 2 since they were already eaten by squirrel 1, and this timeline was created from squirrel 2's timeline, which in turn was created from squirrel 1'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 1 time travels to the original timeline and builds a road between cities 1 and 2.
Squirrel 2 time travels to squirrel 1's timeline, starts in city 1, and eats 2 acorns from city 2.
Squirrel 3 time travels to the original timeline and adds 2 acorns to all cities reachable from city 3 (which is just city 3).
Squirrel 4 time travels to squirrel 3's timeline and builds a road between cities 2 and 3.
Squirrel 5 time travels to squirrel 4's timeline, starts in city 2, and eats 3 the acorns from city 3.
Squirrel 6 time travels to the original timeline, starts in city 2, and eats 2 acorns from city 2.
Squirrel 7 time travels to squirrel 6's timeline, starts in city 2, and does not eat any acorns, as they are no cities reachable from city 2 that have acorns in this timeline.


Comments

There are no comments at the moment.