ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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;
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);
begin
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;
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
for i:=1 to n do
begin
len[i]:=0;
while ch<>'#' do
begin
inc(len[i]);
st[i,len[i]]:=ch;
end;
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);
begin
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;
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.