Problem: http://opc.iarcs.org.in/index.php/problems/HISPDNET

Solution: http://hastebin.com/dawawokivo.avrasm

I used Kruskal’s algo to find the minimum spanning tree from the vertices 2 to N. Yet, it’s leading to a TLE. What am I missing?

Problem: http://opc.iarcs.org.in/index.php/problems/HISPDNET

Solution: http://hastebin.com/dawawokivo.avrasm

I used Kruskal’s algo to find the minimum spanning tree from the vertices 2 to N. Yet, it’s leading to a TLE. What am I missing?

I suspect that TLE is caused by using iostream. In worst case, this probrem has 4*10^6 integers as input . You use ‘ios_base::sync_with_stdio(false);’ . But ‘scanf’ is faster than. Try using ‘scanf’ for input.

(You may feel this answer is hard to read. Because I am not good at English. Sorry.I wish you good luck.)

I used ios_base::sync_with_stdio(false) along with cin.tie(NULL) which should make it even faster, but it’s still leading to a TLE in almost all the test cases. That probably means there is a problem with the logic or some part of the logic in the code, or it’s even leading to an infinite loop somewhere. Thanks anyway. Oh, and I had no trouble reading your answer

I find another problem.You use union-find tree in Kruscal’s algo.

In this data structure,

init:O(n)

union:O(H)

find:O(H)

(H is tree’s height)

I look like your tree’s height is O(N) in worst case. From this, your program is O(N^3). But,two methods union and find are possible to fast,because the height of union-find tree by using two techniques is O(α(n)).

Details on how: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

I wish you good luck.