Hi codeforces! I have been trying this problem (160 D) for quite some while now, and my solution repeatedly TLEs on test case 22. (specifically a case where there are 1e5 edges and all edges are of the same weight.) I have tried debugging it for quite some while now, but am absolutely clueless as to why it TLEs. Could someone please help me out with it?
I am bluntly attaching my code here, which I have commented a bit in an attempt to make it appear a little less junk. Though my code is commented, I am willing to explain any part of my solution in case someone wants it. Any sort of help will be appreciated. :) Solution Link: 95615534
PS: Yeah, I hate debugging blogs too, but please have a look at my solution once before downvoting. :) thx.
Your code is correct you just need to add path compression to Pass the time limit, this small optimization makes the time complexity of the findparent function O(logn) on average.
you can make your code even faster by combining path compression optimization with union by size/rank to achieve nearly constant time queries.
Ac submission : 95618678
reference