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

Обсуждение задачи 1389. Дорожные работы

algorithm
Послано ilucian1 15 ноя 2005 20:08
First of all I suppose the graph is a tree (M=N-1 and all vertices are connected, see the text). Is it a tree? I choose one vertex (let it be 1) and consider it as root. I perform breadth first algorithm starting from the root and obtain vertices in increasing order of distances (in the same time I obtain the parent for each vertex). The result is the array C[1..N]. From N downto 1 I search for available C[i] and P[C[i]] (P[C[i]] is the parent for C[i]). I mark C[i] and P[C[i]] not to be used furthermore (unavailable). The edge [C[i],P[C[i]] is part of solution

and the final result is WA on test 7...
what's wrong ?

Edited by author 15.11.2005 20:32
Re: algorithm
Послано Lucian Ilea 25 авг 2010 17:18
The algorithm was correct but I ignored the output format  ... AC now
Re: algorithm
Послано ErikJ 3 май 2013 18:00
Hi,

I have the same problem with WA #7, in what way was the output format wrong?