My solution to “Chef and College”, from the July 2018 LoC Contest, is getting TLE in one testcase of the second subtask: CodeChef: Practical coding for everyone . 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 : Disjoint Set Union (Union Find) | HackerEarth
link to my soln : CodeChef: Practical coding for everyone
1 Like
Thank you, that was very helpful.
welcome