Editorial for Wesley's Anger Contest 3 Problem 4 - Canadian Construction Crew
Submitting an official solution before solving the problem yourself is a bannable offence.
For a graph with 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.
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 or vertices with odd degrees, and the edges of the graph are connected. We can treat a new requirement as adding to the degree of vertices and . We can determine if the edges are connected by performing a depth first search from any vertex incident to an edge after each update.
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.