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.