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

dimozzz TLE#47 [6] // Задача 1329. Галактическая история 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

Giorgi Saghinadze (Tbilisi SU) Re: TLE#47 [5] // Задача 1329. Галактическая история 11 мар 2007 16:10

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

dimozzz Re: TLE#47 [4] // Задача 1329. Галактическая история 11 мар 2007 20:03

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

KIRILL(ArcSTU) Re: TLE#47 [3] // Задача 1329. Галактическая история 11 мар 2007 20:31

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

Giorgi Saghinadze (Tbilisi SU) Re: TLE#47 [2] // Задача 1329. Галактическая история 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:)

KIRILL(ArcSTU) Re: TLE#47 [1] // Задача 1329. Галактическая история 11 мар 2007 22:25

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

Глащенко Никита Re: TLE#47 // Задача 1329. Галактическая история 5 апр 2009 13:23

Just ingeniously.

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