Discussion @ 1329. Galactic History @ Timus Online Judge

TLE#47

Posted by dimozzz 11 Mar 2007 15:14

I try to solve it for O(n * log(n) * log(n)). I don't understand why I can't passed it? Please help me. I can send my code.

Edited by author 11.03.2007 15:15

Re: TLE#47

Posted by Giorgi Saghinadze (Tbilisi SU) 11 Mar 2007 16:10

you can solve this problem using one DFS. think about it

Re: TLE#47

Posted by dimozzz 11 Mar 2007 20:03

Thank you very much. It's problem very easy... And I'm very stupid. Now I have AC.

Re: TLE#47

Posted by KIRILL(ArcSTU) 11 Mar 2007 20:31

I've solved it with LCA
Does more simple way exists?

Re: TLE#47

Posted by Giorgi Saghinadze (Tbilisi SU) 11 Mar 2007 21:40

KIRILL(ArcSTU) wrote 11 March 2007 20:31

I've solved it with LCA
Does more simple way exists?

Yes of course.

run DFS once and for each vertex remember when you came to this vertex and when you returned there. and then it's very easy to find answer:)

Re: TLE#47

Posted by KIRILL(ArcSTU) 11 Mar 2007 22:25

Thank you for really good idea
It's much more simple to implement then LCA:)

Re: TLE#47

Posted by Глащенко Никита 5 Apr 2009 13:23

Just ingeniously.

Discussion of Problem 1329. Galactic History