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

Обсуждение задачи 1069. Код Прюфера

Показать все сообщения Спрятать все сообщения

Whats wrong with my algo? teamSaratov 28 июл 2006 00:43
Can anyone please help me to find what's wrong with my algo? I've got WA on test #5

1) Reading.
.....a) read i - num of vertex
.....b) increase the i'th power (power - number of vertexs which arre linked with the i-th)
2) Increase the powers of all vertexes except the Nth (the last one).
3) Recovering of thrown queue.
.....for 1 <= i <= N-1 do
.....//it is clear that we had thrown away N-1 vertexes
..........a) Find K - the vertex with minimal power (power=1). We have tree => we can always find such vertex. I'm using the search with barrier.
..........b) Let Power(K)=0 (it means we had thrown it away).
..........c) Decrease the power of i-th given (!) vertex, because it was linked with the Kth.
4) Writing Out.
.....a) for 1 <= i <= N-1 do
..........i) Recover Q - the queue of vertexes, linked with the i-th.
..........ii) QSort(Q);
..........iii) Write sorted Q.
.....b) for i=N do
..........Find in given array of vertexes the entering(-s) of N and write the corresponding vertex in thrown away queue.

I hope it's hardly diffucult to understand what i wrote ;)
Anyway, I can explain it smth if not clear
Re: Whats wrong with my algo? teamSaratov 28 июл 2006 22:33
I've found my mistake (it was in step 4).
So, now I have AC wish everybody the same
;)