记录编号 201308 评测结果 AAAAAAAAAA
题目名称 [USACO Open09] 捉迷藏 最终得分 100
用户昵称 GravatarFoolMike 是否通过 通过
代码语言 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.