Art Academy III: Sabotage

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Java 8 1.0s
PyPy 2 3.0s
PyPy 3 3.0s
Memory limit: 768M

Problem types

After hewmatt10's one and only friend, astrocat879, left his Art Academy, hewmatt10 had been running all across the city in hopes of finding someone that he can replace. Searching far and wide, he eventually stumbles upon the love of his life: [REDACTED]. Wanting to see whether or not hewmatt10 is worthy, [REDACTED] gives him a seemingly impossible task, defined as such:

You are given an undirected, acyclic graph with N nodes and M edges, such that M \le N-1. In other words, you are given a forest of trees. You are also given a special value, called K. Each node will be associated with a group g_i, where 1 \le g_i \le K.

For each connected component, you may choose to do ONE of the following operations:

Operation Description
0 Do nothing with this component.
1 Increase every node's group by 1.
2 Multiply every node's group by 2.
3 Take the bitwise XOR of every node's group by 15.

You must perform operations such that the absolute difference between the number of nodes between two groups x_i and y_i is as FAR AWAY as z_i as possible. You will be asked to do this Q times.

hewmatt10, not wanting to risk his only chance, is relying on YOU to help him. However, because you do NOT want to help him, you have decided to do the EXACT OPPOSITE of what he asks - perform operations such that the absolute difference is EQUAL to z_i.

Input Specification

The first line will contain the integers N, M, K, and Q. (1 \le N \le 3 \cdot 10^2), (0 \le M \le N-1), (2 \le K \le 15), (1 \le Q \le 3 \cdot 10^4).

The next line will contain N spaced integers g_i (1 \le g_i \le K), representing the group of node i (1 \le i \le N).

The next M lines will contain two spaced integers a_i and b_i, indicating that nodes a_i and b_i are connected (1 \le a_i, b_i \le N).

The next Q lines will contain three spaced integers x_i, y_i, and z_i (1 \le x_i, y_i \le K), (1 \le z_i \le N).

Output Specification

For each of the Q questions, output a YES if it is possible to get groups x_i and y_i to have an absolute difference of z_i, and a NO otherwise, followed by a newline.

If the answer is YES, this will then be followed by N spaced integers o_i, followed by a newline, where o_i corresponds to the type of operation performed on node i's connected component to reach z_i. If there are multiple such ways to perform operations, print the arrangement that is lexicographically least.

Clarification: Arrangement refers to the N spaced integers on the second line.


For this problem, you will NOT be required to pass the sample 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.

Subtask 1 [10%]

1 \le N \le 10

K = 2

Q = 1

Subtask 2 [10%]

M = N-1

Subtask 3 [80%]

No additional constraints.

Sample Input

10 7 4 1
1 2 3 3 4 2 3 3 3 2
1 2
1 3
2 4
3 7
5 8
5 9
6 10
1 3 6

Sample Output

0 0 0 0 0 1 0 0 0 1


Operation 1 can be performed on the connected component containing nodes 6 and 10. After performing this operation, there will be 7 nodes with group 3, and 1 node with group 1. This is the lexicographically least way to perform operations such that the absolute difference between groups 1 and 3 is equal to 6.


There are no comments at the moment.