2 / 2
Jul 4

Hi guys,

I'm trying to solve this problem: spoj.pl/problems/TREEISO/4

but it's driving me crazy!!

I'm using the O(n Log n) version of the algorithm "AHU" but it's giving me a (Wrong Answer) over and over again.

the algorithm is:

1- calculating the centre of tree
2 - building the tree levels and save it in array of vectors for each tree: vector [10000][2]
3 - apply the "AHU" algorithm level by level and save tuples of the nodes in array of strings for each tree: string[100000][2]

note: I'm clearing these arrays after solving a level, in other meaning, no 2 levels are saved on memory in the same time.

Would you please provide me with some tricky test cases so I can test my code on?

Thank you in advance!

  • created

    Sep '11
  • last reply

    23d
  • 1

    reply

  • 126

    views

  • 2

    users

  • 2

    links

13 years later

When there are two centroids, you should create a new node and connect the two centroids to it, then remove the edge between the two centroids. Then run AHU algorithm without clearing map (same hash value for different situations may cause issue) with the new node as root.

My code: https://ideone.com/hJBjot1