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

Обсуждение задачи 1022. Генеалогическое дерево

WTF??? O (N^3 log^2 N), or, How I can't calculate the time)
Послано Alibi 20 дек 2014 14:32
THIS IS ACCEPTED CODE
// *CoDeD by Ye.A
# include <iostream>
# include <cstdlib>
# include <cstdio>
# include <vector>
# include <algorithm>

using namespace std;

const int N = 222;
vector <int> g[N], ans;
int n;
bool used[N];

int main ()
{
    //freopen ("input.txt", "r", stdin);
    //freopen ("output.txt", "w", stdout);
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)
        while (1)
        {
            int x;
            scanf ("%d", &x);
            if (!x)
                break;
            g[x].push_back (i);
        }

    while (ans.size() != n)
        for (int i = 1; i <= n; i++)
            if (!used[i] && g[i].empty())
            {
                ans.push_back (i);
                used[i] = true;
                for (int j = 1; j <= n; j++)
                    if (binary_search(g[j].begin(), g[j].end(), i))
                        g[j].erase (lower_bound(g[j].begin(), g[j].end(), i));
            }

    for (int i = 0; i < n; i++)
        printf ("%d ", ans[i]);

    return 0;
}