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

Обсуждение задачи 1198. Коррупция

why tilme limited
Послано SwordHoly 8 мар 2009 19:06
#include<stdio.h>
int k,i,n;
int d[2009];
int f[2009];
int a[2009][2003];
int walk(int x)
{
  int j;
  if(f[i]>0) return 0;
  d[x]=i;
  k++;
  if (k==n) {f[i]=1;return 0;}
  for(j=1;j<=a[x][0];j++)
    if (d[a[x][j]]!=i)
        if (f[a[x][j]]>0) {f[i]=1;f[x]=1;return 1;}
        else {
              f[x]=f[x]+walk(a[x][j]);
        }
  return 0;
}
void main()
{
  int j,t;
  scanf("%d",&n);
  for(i=0;i<=n;i++)
    for(j=0;j<=n;j++)
        a[i][j]=0;

  for(i=1;i<=n;i++)
  {
      do
      {
        scanf("%d",&t);
        if (t!=0) {
                    a[i][0]++;
                    a[i][a[i][0]]=t;
        }
      }while (t!=0);
  }
  for(i=0;i<=n;i++) {d[i]=0;f[i]=0;}
 for(i=1;i<=n;i++)
 {
   k=0;
   walk(i);
 }
for(i=1;i<=n;i++) if (f[i]>0) printf("%d ",i);
printf("0\n");
}
I think it's o(n^2);why tle at test 21th?
Re: why time limited
Послано SwordHoly 8 мар 2009 19:16
who can tell me how to improve this programe?Thanks a lot!