ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1450. Russian Pipelines

TLE 17
Posted by THE_SCORPION 30 Sep 2006 19:13
My program works very quickly, but I have time limit.
I tested my programm many times. In all test time working is not more than 0,2 sec(even with 500 tops and 124750 edges).
Maybe somebody can tell me what is thе 17 test or what is the special trick in this test?
Re: TLE 17
Posted by Kaliningrad SU -J_A_MES-HeadLiner 30 Sep 2006 21:39
Use DP with presorting of course

Edited by author 30.09.2006 21:42
Re: TLE 17
Posted by Eternal 25 Sep 2008 20:25
It's another problem, where i can TLE troubles with Java. I implemented fastest and correct(!) solution :
topological sort + relaxes according to resulting order of vertexes. It works in o(m + n) time, and executing time is very small (0.16 - 0.2 sec) on my computer. I also tried many classes of input/output, but nothing helps. Pls tell me, how can i AC it using Java...
Re: TLE 17
Posted by Eternal 29 Sep 2008 12:34
OMG, I just wrote this algo using C++, and AC in 0.125. Your java compiler is very bad...
Re: TLE 17
Posted by Rustam 22 Jun 2009 02:27
maybe you have problems with processing input/output(in java it's too slow)
i've used ford-bellman algorithm (0.380 sec)