Обсуждение @ 1329. Галактическая история @ Timus Online Judge

TLE#47

Послано dimozzz 11 мар 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

Послано Giorgi Saghinadze (Tbilisi SU) 11 мар 2007 16:10

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

Re: TLE#47

Послано dimozzz 11 мар 2007 20:03

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

Re: TLE#47

Послано KIRILL(ArcSTU) 11 мар 2007 20:31

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

Re: TLE#47

Послано Giorgi Saghinadze (Tbilisi SU) 11 мар 2007 21:40

KIRILL(ArcSTU) писал(a) 11 марта 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

Послано KIRILL(ArcSTU) 11 мар 2007 22:25

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

Re: TLE#47

Послано Глащенко Никита 5 апр 2009 13:23

Just ingeniously.

Обсуждение задачи 1329. Галактическая история