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

Обсуждение задачи 1253. Некрологи

What should I do? I have got TLE.
Послано Koala 4 сен 2003 17:48
program Necrologues;

const
  maxn=9;
  maxrange=1000000;
  maxlen=1000;

var
  a:array [1..maxn,1..maxn] of boolean;
  st:array [1..maxn,1..maxlen] of char;
  l,len,q:array [1..maxn] of longint;
  visit,forbid:array [1..maxn] of boolean;
  n,i,j,k,head,tail:longint;
  ch:char;

  function num(ch:char):boolean;
  var
    k:longint;
  begin
    k:=ord(ch);
    num:=(k>=ord('1')) and (k<=ord('9'));
  end;

  function circle(u:longint):boolean;
  var
    i,j:longint;
  begin
    fillchar(visit,sizeof(visit),0);
    head:=1; tail:=1; q[1]:=u; visit[u]:=true;
    while head<=tail do
    begin
      i:=q[head];
      for j:=1 to n do
        if not(visit[j]) and a[i,j] then
        begin
          visit[j]:=true;
          inc(tail); q[tail]:=j;
        end;
      inc(head);
    end;
    for i:=1 to n do
      if visit[i] and a[i,u] then
      begin
        circle:=true;
        exit;
      end;
    circle:=false;
  end;

  function getlen(i:longint):longint;
  var
    k,j:longint;
  begin
    if l[i]<>-1 then
    begin
      getlen:=l[i];
      exit;
    end;
    l[i]:=0;
    k:=1;
    while k<=len[i] do
      if (st[i,k]='*') and (k<len[i]) and num(st[i,k+1])
        then begin
          j:=ord(st[i,k+1])-ord('0');
          inc(l[i],getlen(j)); if l[i]>maxrange then l[i]:=maxrange+1;
          inc(k,2);
        end
        else begin
          inc(l[i]); if l[i]>maxrange then l[i]:=maxrange+1;
          inc(k);
        end;
    getlen:=l[i];
  end;

  procedure print(i:longint);
  var
    k,j:longint;
  begin
    k:=1;
    while k<=len[i] do
      if (st[i,k]='*') and (k<len[i]) and num(st[i,k+1])
        then begin
          j:=ord(st[i,k+1])-ord('0');
          print(j);
          inc(k,2);
        end
        else begin
          write(st[i,k]);
          inc(k);
        end;
  end;

begin
  readln(n);
  for i:=1 to n do
  begin
    len[i]:=0;
    read(ch);
    while ch<>'#' do
    begin
      inc(len[i]);
      st[i,len[i]]:=ch;
      read(ch);
    end;
    readln;
  end;

  fillchar(a,sizeof(a),0);
  for i:=1 to n do
    for k:=1 to len[i] do
      if (st[i,k]='*') and (k<len[i]) and num(st[i,k+1]) then
      begin
        j:=ord(st[i,k+1])-ord('0');
        a[i,j]:=true;
      end;

  for i:=1 to n do forbid[i]:=circle(i);

  fillchar(visit,sizeof(visit),0);
  head:=1; tail:=1; q[1]:=1; visit[1]:=true;
  while head<=tail do
  begin
    i:=q[head];
    for j:=1 to n do
      if not(visit[j]) and a[i,j] then
      begin
        visit[j]:=true;
        inc(tail); q[tail]:=j;
      end;
    inc(head);
  end;
  for i:=1 to n do
    if visit[i] and forbid[i] then
    begin
      write('#');
      exit;
    end;

  for i:=1 to n do l[i]:=-1;
  l[1]:=getlen(1);
  if l[1]>maxrange then
  begin
    write('#');
    exit;
  end;

  print(1);
end.