Editorial for Wesley's Anger Contest 3 Problem 4 - Canadian Construction Crew


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

Subtask 1

For a graph with N \le 3 nodes and no self loops, it can be shown that there will always be a way to pave the roads; the answer is YES for each query.

Time Complexity: \mathcal O(Q)

Subtask 2

The first observation is that determining whether the road paver can pave all the roads is equivalent to determining whether there is an Eulerian path in the graph. An Eulerian path exists if and only if there are either 0 or 2 vertices with odd degrees, and the edges of the graph are connected. We can treat a new requirement as adding x_i to the degree of vertices a_i and b_i. We can determine if the edges are connected by performing a depth first search from any vertex incident to an edge after each update.

Time Complexity: \mathcal O(N \cdot Q)

Subtask 3

To quickly determine whether a graph is connected, we can instead use the Union-Find data structure, allowing us to quickly query the size of a connected component. The size of the connected component of any arbitrary vertex incident to an edge is equal to the number of vertices we have encountered in the input if and only if the graph is connected. The number of odd degree vertices can be maintained in constant time after each update.

Time Complexity: \mathcal O(N + Q \cdot \alpha(N))


Comments

There are no comments at the moment.