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

Обсуждение задачи 1039. Юбилейная вечеринка

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

WA #13 ? [RSU_Tash]Nodirbek_Kuklamov 9 янв 2012 01:11
Wrong dfs:

    static void dfs(int i){

        used[i] = true;
        if (rank[i] > 0)goes[i] = rank[i];

        int sum_goes = 0, sum_dn_goes = 0;
        for (int to:T[i])
            if (!used[to]){
                dfs(to);
                sum_goes += goes[to];
                sum_dn_goes += dn_goes[to];
            }

        goes[i] = Math.max(goes[i], goes[i] + sum_dn_goes);
        dn_goes[i] += Math.max(sum_goes, sum_dn_goes);

    }


Right dfs:


    static void dfs(int i){
        used[i] = true;
        if (rank[i] > 0)goes[i] = rank[i];
        for (int to:T[i])
            if (!used[to]){
                dfs(to);
                goes[i] += dn_goes[to];
                dn_goes[i] += Math.max(goes[to], dn_goes[to]);
            }
    }