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

Обсуждение задачи 1691. Сложность алгоритма

Is my idea right?
Послано Lebedev_Nicolay[Ivanovo SPU] 17 мар 2009 00:26
If there is cycle in graph then -1,
if path from S to T does not exist then -1,
else 1.
Re: Is my idea right?
Послано svr 15 ноя 2009 09:27
My Ac prog gives 2
on
10 11 1 10
1 5
5 10
5 1
1 2
2 3
3 4
4 2
4 7
7 8
8 7
8 10

By the way.
Answer may be ~ 50000
Also: To find all circles is very difficult.
To find strong components: this is helped me to break long sequence of TLE
Re: Is my idea right?
Послано Lebedev_Nicolay[Ivanovo SPU] 15 ноя 2009 15:26
Can you give an idea of solution with StrConnected Comp?
Re: Is my idea right?
Послано svr 15 ноя 2009 20:44
You must take in account that only 26 TopCoders has solved
this probem. It rather involved and demand
education level.
For your training only I can said:
1. If stronng comp is not simple circle and
can be go in from s and after t is achivebale then:  -1
2. If only simple circles we met then:  it's number mines one.
it is coin change asymptotics.
Re: Is my idea right?
Послано bsu.mmf.team 13 мар 2010 02:20
I'd say if the path from S to T does not exist then we should output 0.