Re: WA on #14.Can somebody give me some tests to help me find out the mistakes?
Posted by
yuyan 19 Apr 2009 20:26
Up to now.I can't find what's wrong with my program?
I use greedy algorithm with heap.
Here is my code:
program mini;
const
maxn=201000;
var
h,p,l,list:array [0..maxn] of longint;
vis:array [0..maxn] of boolean;
g,next,v,d,g1,next1,v1:array [0..maxn] of longint;
i,j,k,m,n,r,q,e,t:longint;
ans:qword;
procedure insert(u:longint);
begin
inc(e);next[e]:=g[u];g[u]:=e;v[e]:=r;d[e]:=j;
end;
procedure ins(u:longint);
begin
next1[r]:=g1[u];g1[u]:=r;v1[r]:=r;
end;
procedure swap(var x,y:longint);
var t:longint;
begin
t:=x;x:=y;y:=t;
end;
procedure up(k:longint);
begin
while (k>1) and (h[k shr 1]<h[k]) do
begin
swap(h[k shr 1],h[k]);
swap(l[k shr 1],l[k]);
p[l[k shr 1]]:=k shr 1;p[l[k]]:=k;
k:=k shr 1;
end;
end;
procedure down(k:longint);
begin
repeat
j:=k;
if (j shl 1<=t) and (h[j shl 1]>h[k]) then k:=j shl 1;
if (j shl 1+1<=t) and (h[j shl 1+1]>h[k]) then k:=j shl 1+1;
if j<>k
then begin
swap(h[j],h[k]);
swap(l[j],l[k]);
p[l[j]]:=j;p[l[k]]:=k;
end;
until j=k;
end;
procedure init;
begin
read(n,m,k,q);
for r:=1 to k do
begin
read(i,j);if i=j then repeat until false;
if i>j then swap(i,j);
insert(i);
ins(j);
end;
end;
procedure solve;
begin
ans:=0;t:=0;
for i:=1 to n do
begin
r:=g1[i];
while r<>0 do
begin
if vis[v1[r]]
then begin
inc(ans);list[ans]:=v1[r];
inc(m);vis[v1[r]]:=false;
h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t);
down(p[v1[r]]);
end;
r:=next1[r];
end;
r:=g[i];
while r<>0 do
begin
dec(m);vis[v[r]]:=true;
inc(t);l[t]:=v[r];p[v[r]]:=t;h[t]:=d[r];
up(t);
r:=next[r];
end;
while m<0 do
begin
vis[l[1]]:=false;h[1]:=h[t];l[1]:=l[t];p[l[1]]:=1;dec(t);
down(1);
inc(m);
end;
r:=g1[i];
while r<>0 do
begin
if vis[v1[r]]
then begin
inc(ans);list[ans]:=v1[r];
inc(m);vis[v1[r]]:=false;
h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t);
down(p[v1[r]]);
end;
r:=next1[r];
end;
end;
end;
procedure print;
begin
writeln(ans*q);
if ans=0 then exit;
for i:=1 to ans-1 do write(list[i],' ');writeln(list[ans]);
end;
begin
assign(input,'mini.in');reset(input);
assign(output,'mini.out');rewrite(output);
init;
solve;
print;
close(input);close(output);
end.
Could you tell me what's wrong with my program?Or let me refer to your AC program?
Thanks.