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

Обсуждение задачи 1280. Topological Sorting

Anton [SUrSU#6] WA#33 [8] // Задача 1280. Topological Sorting 25 июн 2006 01:42
Who can give me some tricky tests for this problem, please!
PSV Re: WA#33 [7] // Задача 1280. Topological Sorting 3 ноя 2006 04:55
May be you need a more tricky algo? It's unable to have WA with this problem (quite simple algo)
Jabarov_Roman Re: WA#33 [6] // Задача 1280. Topological Sorting 10 ноя 2006 02:04
Please help, i have the same problem but i don't know where is my error here is code
#include <iostream>
using namespace std;
int power[1005];
int deg[1005];
int mas[1005][1005];
int n,m;
int answers[1006];
void input()
{
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        mas[a][power[a]++] = b;
        deg[b]++;
    }
    for(int i=0;i<n;i++)
        cin>>answers[i];
}
void solve()
{
    for(int i=0;i<n;i++)
    {
        if (deg[answers[i]]>0)
        {
            cout<<"NO";
            return;
        }
        for(int j=0;j<power[answers[i]];j++)
            deg[mas[answers[i]][j]] --;
    }
    cout<<"YES";
}
int main()
{
    input();
    solve();
    return 0;
}
Nechaev Ilya (Rybinsk SAAT) Re: WA#33 // Задача 1280. Topological Sorting 10 ноя 2006 04:00
I don't know what are you doing, but you need just check M conditions for given sequence. I don't know what can be wrong.

Edited by author 10.11.2006 04:29
Nechaev Ilya (Rybinsk SAAT) Re: WA#33 [4] // Задача 1280. Topological Sorting 10 ноя 2006 04:20
Haha. I just changed
     int mas[1005][1005];
to
     int mas[1005][10005];
and get AC.
I think that each limitation can occur in the input more than once i.e. some limitations can be equal    :-p

Advice: this solution use too much memory. Really you need less than 1 Mb.

Edited by author 10.11.2006 14:02
WhiteRabbit Re: WA#33 // Задача 1280. Topological Sorting 10 ноя 2006 18:42
Thank you for advise. Now i just changed adjanced list stored in array to vector<vector<int> > . And my programm used only 860 Kb.
Jabarov_Roman Re: WA#33 [1] // Задача 1280. Topological Sorting 10 ноя 2006 23:42
Nechaev Ilya (Rybinsk SAAT) писал(a) 10 ноября 2006 04:20
Haha. I just changed
     int mas[1005][1005];
to
     int mas[1005][10005];
and get AC.
I think that each limitation can occur in the input more than once i.e. some limitations can be equal    :-p

Advice: this solution use too much memory. Really you need less than 1 Mb.

Edited by author 10.11.2006 14:02

I'm very appreciate you. I used vector<vector<int> > and eventually got AC:-)
LLL Re: WA#33 // Задача 1280. Topological Sorting 2 окт 2016 22:16
Thx!
MAK Re: WA#33 // Задача 1280. Topological Sorting 12 окт 2009 03:42
Thank you for the advice about limitations!