ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1145. Rope in the Labyrinth

How to avoid TL?
Posted by misha 25 Dec 2002 10:01
I can't imagine, how to solve this problem in 1 second. Please, help!
Re: How to avoid TL?
Posted by TheBeet 25 May 2004 15:15
Just BFS two times.
First BFS:
>Start from any place
>>Then Find The one which you arrive at last.
Second BFS:
>Start from this place
>>Then the distance you go farthest is the Answer.

Edited by author 29.05.2004 08:49
How large should the queue be?
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 26 Oct 2004 04:44
I set its size to 50000, and got AC with 989K memory. But I suppose it needn't be so large. Who can tell me the upper bound of its size?

Edited by author 26.10.2004 15:37
You can use two queues.
Posted by Fu Dong 30 May 2005 18:02
I only used 325KB with BFS.

Edited by author 30.05.2005 18:21
Re: How to avoid TL?
Posted by program 20 Dec 2007 16:55
First BFS:
Start from any place
Then Find The one which you arrive at last.
Second BFS:
Start from this place
Then the distance you go farthest is the Answer.

I don't understand why does it work?
First BFS may result many different place. Or last element of the queue? But wait how about the orders of the direction?

Second BFS
why?
Re: How to avoid TL?
Posted by Denis Koshman 4 Aug 2008 13:35
I make tree rooted (parent info consumes only 1Mb - I store direction to the parent). Then for each node I find distance to deepest child (+4Mb). Then for each node I find 2nd maximum, the answer is max(max1+max2). It's general algo for any tree, and it worked here at around 0.093 sec.