Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## P党的一点贡献(数据生成器+AC程序)

Posted by zhouzixuan at 2014-06-27 17:08:39 on Problem 3728
dataer:
var
n,m,i,j,k,x,y:longint;
begin
assign(output,'1.in'); rewrite(output);
for i:=1 to n do writeln(random(50000)+1);
for i:=2 to n do writeln(i,' ',random(i-1)+1); writeln(m);
for i:=1 to m do writeln(random(n)+1,' ',random(n)+1);
end.

AC code:
{\$inline on}
type
edge=record
x,y,next:longint;
end;
sets=record
minv,maxv,tmax,bmax,father,v:longint;
end;
var
b,bb:array [0..100001] of edge;
a,aa,ans,father:array [0..50001] of longint;
v:array [0..50001] of boolean;
c:array [0..50001] of sets;
n,m,tot1,tot2:longint;
function max(x,y:longint):longint; inline;
begin
if x>y then exit(x) else exit(y);
end;
function min(x,y:longint):longint; inline;
begin
if x<y then exit(x) else exit(y);
end;
begin
inc(tot1);
b[tot1].x:=y;
b[tot1].next:=a[x];
a[x]:=tot1;
end;
begin
inc(tot2);
bb[tot2].x:=y;
bb[tot2].y:=z;
bb[tot2].next:=aa[x];
aa[x]:=tot2;
end;
procedure init;
var
i,x,y:longint;
begin
readln(n); tot1:=0; tot2:=0; fillchar(a,sizeof(a),0); fillchar(aa,sizeof(aa),0); fillchar(v,sizeof(v),true);
for i:=1 to n do begin c[i].father:=i; readln(c[i].v); c[i].minv:=c[i].v; c[i].maxv:=c[i].v; end;
end;
function getfather(x:longint):longint;
var
pre:longint;
begin
if x=c[x].father then exit(x); pre:=c[x].father;
c[x].father:=getfather(c[x].father);
c[x].tmax:=max(c[pre].maxv-c[x].minv,max(c[pre].tmax,c[x].tmax));
c[x].bmax:=max(c[x].maxv-c[pre].minv,max(c[pre].bmax,c[x].bmax));
c[x].minv:=min(c[x].minv,c[pre].minv);
c[x].maxv:=max(c[x].maxv,c[pre].maxv);
exit(c[x].father);
end;
procedure union(x,y:longint);
begin
x:=getfather(x); y:=getfather(y);
c[y].father:=x;
end;
procedure dfs(x,pre:longint);
var
p,pp,lca,minv,maxv,maxs,now:longint;
begin
p:=a[x]; father[x]:=pre;
while p<>0 do
begin
pp:=b[p].x; if pp=pre then begin p:=b[p].next; continue; end;
dfs(pp,x); union(x,pp); p:=b[p].next;
end;
v[x]:=false; p:=aa[x];
while p<>0 do
begin
pp:=bb[p].x; if v[pp] then begin p:=bb[p].next; continue; end;
lca:=getfather(pp); minv:=c[x].v; maxv:=c[x].v; maxs:=0; now:=x;
if bb[p].y<=m then
begin
while now<>lca do
begin
maxs:=max(maxs,c[now].v-minv);
minv:=min(minv,c[now].v); now:=father[now];
end;
ans[bb[p].y]:=max(c[pp].maxv-minv,max(maxs,c[pp].bmax));
end;
if bb[p].y>m then
begin
while now<>lca do
begin
maxs:=max(maxs,maxv-c[now].v);
maxv:=max(maxv,c[now].v); now:=father[now];
end;
ans[bb[p].y-m]:=max(maxv-c[pp].minv,max(maxs,c[pp].tmax));
end;
p:=bb[p].next;
end;
end;
procedure main;
var
i:longint;
begin
for i:=1 to m do writeln(ans[i]);
end;
procedure openfile;
begin
assign(input,'1.in');
reset(input);
assign(output,'1.out');
rewrite(output);
end;
begin
openfile;
init;
dfs(1,0);
main;
end.

Followed by: