Hello, Codeforces. Recently I’ve been watching some educational contests, and I came across problem 609E - Minimum spanning tree for each edge. As we can see, it doesn’t have the “binary search” tag, but I found a nice solution using Kruskal’s algorithm together with parallel binary search. This is my AC submission 356579606.

First, I build the minimum spanning tree of the graph. Then, for every edge, I find the moment during Kruskal’s algorithm when the two endpoints of that edge are already connected. At that moment, if we added this edge instead of one of the edges chosen by Kruskal, we would create a cycle. Replacing the corresponding edge from the MST with this one produces another spanning tree with a slightly larger total cost — and that cost is exactly the answer for that edge. The correctness of this idea is very similar to the correctness proof of Kruskal’s algorithm.

So the only thing that remains is to find that “moment” for each edge. For a single edge, we could find it with a standard binary search, but each step requires rebuilding a DSU. This allows us to use parallel binary search, giving a complexity of O(m * log(n) * a(n)), where a(n) is Ackerman number of n, which is OK. For me this problem must have 'greedy' and 'binary search' tags too.

I have one friend aren_dance. His condtribution was near to -25 and he concluded to leave that accaunt and start coding with new one. He was solving 3 problems from div 2 but he is rating have stucked at 1100. In his new account he's solving same 3 problems and near to same time but he easyly managed to get 1360. And we have wroten div 3 we writed it close to each other like both were close to 6000 position. He 1200 became 1260. I 1420 became 1360(my cont.--14 at that moment his-0. So question stays-Does bad contribution make to gain rating harder?