Problem Link:Difficulty:Medium Prerequisites:Disjoint Set Union Problem:Maintain the size of the most populated region after each query. Explanation:Solution for the subtask 1 (21 points):The solution of this subtask is to use breadth first search after applying each query to find all the regions' city sets. If we have all the regions' cities sets, we can easily find the maximal populated region. Let's describe this approach in more details. Let's denote: 1) Integer array $P$, where $P[i]$ is the population of city numbered the $i$^{th}. 2) Boolean array $D$, where $D[j]$ is true, if the road numbered the $j$^{th} has been destroyed, and false otherwise. 3) Adjacency list $Adj$. We can store this list efficiently, for example, using STL vector in C++. For every adjacent node, let's store a structure, containing the following fields:
Having all this, we can process the queries in the following way:
Now, how to find the size of the maximal populated region. We will make use of queue data structure. Let's iterate through all the nodes. Whenever we find a node which was not included in any connected component, we start the breadth first search. Let's describe it in brief:
Let's denote Boolean array $Used$, where $Used[i]$ is true, if $i$^{th} city was added to queue, and false otherwise. The pseudocode of the algorithm for finding the size of the most populated region is given below.
The complexity is $O(Q*(N+M))$. Solution for all subtasks:We will use the data structure called Disjoint Set Union. Let's have $N$ elements numbered $1$ to $N$ and $N$ sets. Initially, the $i$^{th} set contains the $i$^{th} element. Disjoint Set Union maintains two basic operations: 1) Uniting two sets. 2) Finding the set containing the given element. The amortized time per operation is $O(\alpha(N))$, where $\alpha(N)$ is less than $5$ for all remotely practical values of $N$. Note that you don't have to output the size of the most populated region before reading the next query. So, you can read all the queries in advance and solve the task in reverse order. Assume that all $Q$ queries were performed. Let's add all connected components (regions) to the DSU. Obviously, we can determine the most populated region. Let's create the DSU with $N$ elements denoting the cities and $N$ sets denoting the regions. Along with each set (say, the $X$^{th}), let's maintain the value of $P[X]$, denoting the total population of the cities in the $X$^{th} set. Now, the DSU corresponds to the road system with $N$ cities, given populations and without roads. Note that we should take the populations that are obtained after the performing of all the queries. Now, assume that all the queries has already been performed. Then, there is a set of roads, which has not been deleted. Let's add all of them. The addition of the road is simply merging two corresponding sets in the DSU structure. Since we have one nonstandard operation here, namely, handling the sizes of the regions, letТs give a pseudocode for it. Given that we need to add a road connecting the city numbered the $X$^{th} and the city numbered the $Y$^{th}.
Now, let's "rollback" the queries starting with the last one. The "rollback" of the change population query is changing the value of the corresponding $P[X]$, and the "rollback" of the road deletion query is adding the road like we've described above. Meanwhile, we can also maintain a priority queue of an STL set for determining the size of the largest region quickly. This way, we can answer on the maximal region population in $O(\log N)$. The complexity is O($N + M \alpha(N) + Q \log N$). Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 22 Dec '15, 06:12

Answer is hidden as author is suspended. Click here to view.
answered 30 Dec '15, 16:48

@ayushtomar: Process the queries offline from last to first, so instead of deleting edges you're actually adding them. answered 27 Dec '15, 16:16
Sir sir _/_
(27 Dec '15, 19:52)
@AnonymousBunny 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.
(30 Dec '15, 20:13)

Add the problems to practice section! And nice editorial! answered 27 Dec '15, 15:01

I found out the connected components for after each query and found out the max in those components. Was it an overkill for this problem? answered 27 Dec '15, 18:06

@aminoacid, it was not an overkill for this problem. As told by the editorialist as well, use bfs can do the trick for 30 points. I think what went wrong in your case was the recusrive call stack because of the tarjan algorithm you applied, giving you segmentation fault (stack size reached the upper limit due to large number of recursive calls). You may refer to my solution for 30 points, similar to the way editorialist has written. https://www.codechef.com/viewsolution/9024537 answered 27 Dec '15, 18:55
@likecs please tell me what is that priority queue thing. My code is taking time because I am finding max region in O(n).
(07 Jan '16, 18:26)

Why is my code giving wrong answer for small subtasks?
answered 27 Dec '15, 19:25

@admin Why the hell are the codechef's editorialist's and tester's code NEVER visible ? answered 31 Dec '15, 12:39
@theweblover007 Tester's code is visible.
(31 Dec '15, 22:21)

Hello, I've been solving this problem for about a month (with breaks OFC), but I still can't get something; My DSU solution passes through all subtask's tests, but it doesn't work on main tests; Yes, I used "long long" and gave range of (1e5 * 5 + 1), everywhere, please can you say my mistake or make tests visible, it's really getting erratating, thanks! answered 09 Jan '18, 15:25
