TLE in only one test case of COLCHEF



My solution to “Chef and College”, from the July 2018 LoC Contest, is getting TLE in one testcase of the second subtask: . I tried using a simple union-find approach, and would like to know how the algorithm could be optimized. Thanks.


Use DSU data structure to solve ,your code is giving tle just because you run a O(N) loop to make them friend,where it can be done with DSU with very less constant time complexity.

link of DSU :

link to my soln :


Thank you, that was very helpful.


welcome :slight_smile: