https://www.codechef.com/LTIME31/problems/ABROADS
what data structure will be used to solve this problem, can any one please write editorial to it.
Also add links to similar kinds of problems.
and please tell how this code is working:
https://www.codechef.com/viewsolution/9023693
This question has two type of queries:
Had query 1 would have been insert an edge in graph, we would have Disjoint Set Union Data Structure and easily solved this question, but here it is to delete.
Solution: First of all create disjoint set union on graph after deleting all edges which are going to deleted by some query. In other words, graph should be what it would have been after processing all queries in input. Now start answering queries from last query(i.e. in reverse order). Each “delete edge” query is now changed to “insert edge” query which can be handled by dsu easily.
@sumeet_varma already added the explanation. I’ll just point you to some similar problems on codeforces.
If you want to practice on codechef only , just search for dsu tag on this page.
@arpit728 Editorial is already available for this problem. If you don’t understand something there,just ask in the comments.
@sarvagya3943:
While we process the queries in reverse order, if the query encountered is of “p” type then how we would be knowing, what was the population before that query.(Referring the editorial).
@arpit728 You can use Stack for each index of population array.
While processing the query in online mode whenever you encounter to change the population just push it into stack of particular index of array.
While doing Offline query in reverse order just pop the elements from stack to get back the previous population.
Second Approach Maintain a new array of same size as that of number of queries. While doing online query, whenever you encounter to change the popualtion of the town store the current value of that population into new array at same index that of query and update the population array.
Later on you can easily access the previous value. See my implementation for this.
@arpit728 I think we can store the previous value at the cost of memory. If you find any better approach do please tell me.