ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1253. Necrologues

What should I do? I have got TLE.
Posted by Koala 4 Sep 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.