ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1450. Российские газопроводы

TLE 17
Послано THE_SCORPION 30 сен 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
Послано Kaliningrad SU -J_A_MES-HeadLiner 30 сен 2006 21:39
Use DP with presorting of course

Edited by author 30.09.2006 21:42
Re: TLE 17
Послано Eternal 25 сен 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
Послано Eternal 29 сен 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
Послано Rustam 22 июн 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)