STONE1 - Rải sỏi

Tác giả: RR

Ngôn ngữ: Pascal

PROGRAM STONE1;
CONST
  fi='';
  fo='';
  maxn=400;
TYPE
  lifo=^ds;
  ds=record data:integer; next:lifo; end;
  mang=array[1..maxn] of integer;
VAR
  n:integer;
  Ke:array[1..maxn] of lifo;
  sc,min:array[1..maxn] of integer;
Procedure Prepare;
Var
  i:integer;
Begin
  For i:=1 to n do sc[i]:=0;
  For i:=1 to n do
    begin
      New(ke[i]);
      Ke[i]:=nil;
    end;
End;
Procedure Add(u:integer;var k:lifo);
Var
  p:lifo;
Begin
  New(p); p^.data:=u; p^.next:=k; k:=p;
End;
Procedure ReadInput;
Var
  f:text;
  i,j,u,count:integer;
  xet:array[1..maxn] of boolean;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,n);
  Prepare; count:=1;
  For i:=1 to n do xet[i]:=false;
  While not Eof(f) do
  begin
    Read(f,i);
    Read(f,sc[i]);
    For j:=1 to sc[i] do
      begin
        Read(f,u);
        Add(u,ke[i]);
        If not xet[u] then inc(count);
        xet[u]:=true;
      end;
    If count=n then exit;
  end;
  Close(f);
End;
Function max(a,b:integer):integer;
Begin
  If a>b then max:=a else max:=b;
End;
Procedure QuickSort(var a:mang;n:integer);
  Procedure Sort(l,r:integer);
  Var
    i,j:integer;
    tg,x:integer;
  Begin
    i:=l; j:=r; x:=a[(l+r) div 2];
    repeat
      While a[i]>x do inc(i);
      While a[j]<x do dec(j);
      If i<=j then
        begin
          tg:=a[i]; a[i]:=a[j]; a[j]:=tg;
          inc(i); dec(j);
        end;
    until i>j;
    If i<r then Sort(i,r);
    If l<j then Sort(l,j);
  End;
Begin
  Sort(1,n);
End;
Procedure Visit(u:integer);
Var
  p:lifo;
  dem:integer;
  a:mang;
Begin
  min[u]:=1;
  If sc[u]=0 then exit;
  p:=Ke[u]; dem:=0;
  While p<>nil do
  with p^ do
    begin
      Visit(data);
      inc(dem);
      a[dem]:=min[data];
      p:=next;
    end;
  QuickSort(a,sc[u]);
  For dem:=1 to sc[u] do
    If a[dem]+dem-1>min[u] then min[u]:=a[dem]+dem-1;
End;
Procedure WriteOutput;
Var
  f:text;
Begin
  Assign(f,fo); Rewrite(f);
  Writeln(f,min[1]);
  Close(f);
End;
BEGIN
  ReadInput;
  Visit(1);
  WriteOutput;
END.

Download