记录编号 |
201308 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[USACO Open09] 捉迷藏 |
最终得分 |
100 |
用户昵称 |
FoolMike |
是否通过 |
通过 |
代码语言 |
Pascal |
运行时间 |
0.088 s |
提交时间 |
2015-10-30 14:59:22 |
内存使用 |
1.31 MiB |
显示代码纯文本
var
n,m,i,j,a,b,ans,ans1,ans3:longint;
f:array[1..100000,1..2]of longint;
g:array[1..20000,1..2]of longint;
dist:array[1..20000]of longint;
tz:array[0..1,0..20000]of longint;
procedure kuaipai(l,r:longint);
var
i,j,x:longint;
y:longint;
begin
i:=l;j:=r;x:=f[(i+j) div 2,1];
repeat
while f[i,1]<x do inc(i);
while f[j,1]>x do dec(j);
if i<=j then
begin
y:=f[i,1];f[i,1]:=f[j,1];f[j,1]:=y;
y:=f[i,2];f[i,2]:=f[j,2];f[j,2]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then kuaipai(i,r);
if l<j then kuaipai(l,j);
end;
begin
assign(input,'hideseek.in');
reset(input);
assign(output,'hideseek.out');
rewrite(output);
read(n,m);
for i:=1 to m do
begin
read(f[i,1],f[i,2]);
f[i+m,1]:=f[i,2];
f[i+m,2]:=f[i,1];
end;
kuaipai(1,2*m);
j:=f[1,1];
g[j,1]:=1;
for i:=2 to 2*m do
if f[i,1]<>j then
begin
g[j,2]:=i-1;
j:=f[i,1];
g[j,1]:=i;
end;
g[j,2]:=i;
fillchar(dist,sizeof(dist),$7f);
dist[1]:=0;
tz[0,0]:=1;
tz[0,1]:=1;
a:=1;ans:=0;
repeat
a:=(a+1) mod 2;
b:=(a+1) mod 2;
tz[b,0]:=0;
if tz[a,0]=0 then break;
inc(ans);
for i:=1 to tz[a,0] do
for j:=g[tz[a,i],1] to g[tz[a,i],2] do
if dist[f[j,2]]>ans then
begin
inc(tz[b,0]);
tz[b,tz[b,0]]:=f[j,2];
dist[f[j,2]]:=ans;
end;
until 1>2;
dec(ans);
ans1:=0;ans3:=0;
for i:=1 to n do
if dist[i]=ans then
begin
inc(ans3);
if ans1=0 then ans1:=i;
end;
writeln(ans1,' ',ans,' ',ans3);
close(input);
close(output);
end.