BOSS - Ai là sếp

Tác giả: ll931110

Ngôn ngữ: Pascal

program BOSS;
const
  input  = '';
  output = '';
  maxn = 30000;
  maxv = 1000000;
type
  pnode = ^tnode;
  tnode = record
    val: longint;
    link: pnode;
  end;
var
  id,h,s,tmp,tmppos: array[1..maxn] of longint;
  tx,pre,nchi: array[1..maxn] of longint;
  idpos: array[1..maxv] of longint;
  a: array[1..maxn] of pnode;
  free: array[1..maxn] of boolean;
  i,nTest: longint;
  n,q: longint;
  fi,fo: text;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

procedure init;
var
  i: longint;
begin
  readln(fi, n, q);
  for i := 1 to n do readln(fi, id[i], s[i], h[i]);
end;

procedure sw(var x,y: longint);
var
  z: longint;
begin
  z := x;  x := y;  y := z;
end;

procedure swap1(i,j: longint);
begin
  sw(id[i],id[j]);  sw(h[i],h[j]);  sw(s[i],s[j]);
end;

procedure sort1(lo,hi: longint);
var
  i,j,p: longint;
begin
  if lo >= hi then exit;
  i := lo;  j := hi;  p := s[random(hi - lo + 1) + lo];

  repeat
    while s[i] < p do inc(i);
    while s[j] > p do dec(j);
    if i <= j then
      begin
        if i < j then swap1(i,j);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort1(lo,j);  sort1(i,hi);
end;

procedure swap2(i,j: longint);
begin
  sw(tmp[i],tmp[j]);  sw(tmppos[i],tmppos[j]);
end;

procedure sort2(lo,hi: longint);
var
  i,j,p: longint;
begin
  if lo >= hi then exit;
  i := lo;  j := hi;  p := tmp[random(hi - lo + 1) + lo];

  repeat
    while tmp[i] < p do inc(i);
    while tmp[j] > p do dec(j);
    if i <= j then
      begin
        if i < j then swap2(i,j);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort2(lo,j);  sort2(i,hi);
end;

//BIT operations
procedure update(x,val: longint);
begin
  while x > 0 do
    begin
      if tx[x] > val then tx[x] := val;
      x := x - (x and -x);
    end;
end;

function calc(x: longint): longint;
var
  r: longint;
begin
  r := maxv;
  while x <= maxn do
    begin
      if r > tx[x] then r := tx[x];
      x := x + (x and -x);
    end;

  calc := r;
end;

procedure add(x,y: longint);
var
  p: pnode;
begin
  new(p);
  p^.val := y;
  p^.link := a[x];
  a[x] := p;
end;

procedure DFS(u: longint);
var
  p: pnode;
begin
  free[u] := false;
  p := a[u];

  while p <> nil do
    begin
      if p^.val <> pre[u] then
        begin
          if free[p^.val] then DFS(p^.val);
          nchi[u] := nchi[u] + nchi[p^.val] + 1;
        end;

      p := p^.link;
    end;
end;

procedure precom;
var
  i,t: longint;
begin
  sort1(1,n);
  for i := 1 to n do s[i] := i;

  tmp := h;
  for i := 1 to n do tmppos[i] := i;
  sort2(1,n);

  t := 1;  h[tmppos[1]] := 1;
  for i := 2 to n do
    begin
      if tmp[i] > tmp[i - 1] then inc(t);
      h[tmppos[i]] := t;
    end;

  for i := 1 to n do idpos[id[i]] := i;

  //Find boss
  for i := 1 to n do a[i] := nil;
  for i := 1 to maxn do tx[i] := maxv;
  fillchar(pre, sizeof(pre), 0);
  fillchar(nchi, sizeof(nchi), 0);

  for i := n downto 1 do
    begin
      t := calc(h[i]);
      if t <> maxv then
        begin
          pre[i] := t;
          add(t,i);
        end;
      update(h[i],i);
    end;

  fillchar(free, sizeof(free), true);
  for i := 1 to n do if free[i] then DFS(i);
end;

procedure query;
var
  i,t: longint;
begin
  for i := 1 to q do
    begin
      readln(fi, t);
      t := idpos[t];
      if pre[t] = 0 then write(fo, 0) else write(fo, id[pre[t]]);
      writeln(fo, ' ', nchi[t]);
    end;
end;

begin
  openfile;

  readln(fi, nTest);
  for i := 1 to nTest do
    begin
      init;
      precom;
      query;
    end;

  closefile;
end.

Download