HELP!!! why i got TLE? (+)
Posted by
zhangqi 17 Apr 2003 14:57
i use 0(n^2) algo, but i got TlE.
here is my code
-----------------------------------------------
program The_Prufer_Code;
const maxn=7500;
var n:integer;
a:array[1..maxn]of integer;
num:array[1..maxn]of integer;
link:array[1..maxn,1..2]of integer;
mark:array[1..maxn]of integer;
ans:array[1..maxn]of boolean;
total:integer;
procedure init;
var i:integer;
begin
fillchar(num,sizeof(num),0);
fillchar(a,sizeof(a),0);
n:=0;
while not eof do begin
inc(n);
read(a[n]);
inc(num[a[n]]);
end;
inc(n);
end;
procedure work;
var i,j:integer;
begin
fillchar(link,sizeof(link),0);
total:=0;
for i:=1 to n-1 do begin
for j:=1 to n-1 do if num[j]=0 then begin
inc(total);
link[total,1]:=a[i];
link[total,2]:=j;
dec(num[j]);
break;
end;
dec(num[a[i]]);
end;
end;
procedure print;
var i,j,k:integer;
begin
fillchar(mark,sizeof(mark),0);
for i:=1 to n do begin
write(i,':');
fillchar(ans,sizeof(ans),0);
for j:=1 to total do if mark[j]<2 then begin
for k:=1 to 2 do
if link[j,k]=i then begin
ans[link[j,3-k]]:=true;
inc(mark[j]);
break;
end;
end;
for j:=1 to n do
if ans[j] then write(' ',j);
writeln;
end;
end;
begin
Init;
Work;
Print;
end.
O(N^2) is bad, use heaps --> (O log N) --> AC in 0.12 sec ---> :)
If you encourage problems I can post my code.
problems with 69 make me think of bad things. also O(N) works, and now i see why use heaps :) ~nt~
Posted by
foxX 17 Apr 2003 21:00
> If you encourage problems I can post my code.
Re: problems with 69 make me think of bad things. also O(N) works, and now i see why use heaps :) ~nt~
Please someone can post his AC because for 6 months i can't take AC
with a correct source (i'm sure of it...)