TLE in only one test case of COLCHEF

union-find

#1

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


#2

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 : https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/

link to my soln : https://www.codechef.com/viewsolution/19357712


#3

Thank you, that was very helpful.


#4

welcome :slight_smile: