QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417662#4113. 寻宝游戏LynkcatCompile Error//Pascal2.4kb2024-05-22 20:33:062024-05-22 20:33:08

Judging History

你现在查看的是最新测评结果

  • [2024-05-22 20:33:08]
  • 评测
  • [2024-05-22 20:33:06]
  • 提交

answer

uses Gset,Gutil,math;
type
  cmp=specialize Tless<longint>;
  sets=specialize Tset<int64,cmp>;
  rec=record
  x,next,dis:longint;
  end;
var f,d:array[0..100000,0..20] of int64;
    dian,dep,h,xu:array[0..100000] of longint;
    b:array[0..100000] of boolean;
    q:array[0..200000] of rec;
    k1,n,m,i,x,y,z,u,cnt1,cnt,k:longint;
    ans:int64;
    s:sets;
procedure ad(x,y,z:longint);
begin
  inc(cnt);
  q[cnt].x:=x;q[cnt].dis:=z;q[cnt].next:=h[y];
  h[y]:=cnt;
end;
procedure dfs(k,l,dist:longint);
var t,i:longint;
begin
  inc(k1);
  dian[k1]:=k;xu[k]:=k1;
  dep[k]:=dep[l]+1;
  f[k,0]:=l;d[k,0]:=dist;
  for i:=1 to trunc(log2(dep[k])) do
  begin
    f[k,i]:=f[f[k,i-1],i-1];
    d[k,i]:=d[k,i-1]+d[f[k,i-1],i-1];
  end;
  t:=h[k];
  while t>0 do
  begin
    if q[t].x<>l then dfs(q[t].x,k,q[t].dis);
    t:=q[t].next;
  end;
end;
function lca(x,y:longint):int64;
var i,t:longint;
begin
  lca:=0;if (x=0)or(y=0) then exit(0);
  if dep[x]<dep[y] then
  begin
    t:=x;x:=y;y:=t;
  end;
  for i:=20 downto 0 do
  begin
    if dep[f[x,i]]>=dep[y] then
    begin
      lca:=lca+d[x,i];
      x:=f[x,i];
    end;
    if x=y then exit;
  end;
  for i:=20 downto 0 do
    if f[x,i]<>f[y,i] then
    begin
      lca:=lca+d[x,i]+d[y,i];
      x:=f[x,i];
      y:=f[y,i];
    end;
  lca:=lca+d[x,0]+d[y,0];
end;
begin
  readln(n,m);ans:=0;
  s:=sets.create;
  s.insert(-maxlongint);
  s.insert(maxlongint);
  for i:=1 to n-1 do
  begin
    readln(x,y,z);
    ad(x,y,z);
    ad(y,x,z);
  end;
  dfs(1,0,0);
  for i:=1 to m do
  begin
    readln(u);
    if b[u] then
    begin
      x:=s.findgreater(xu[u]).data;if x=maxlongint then x:=s.findgreater(-maxlongint).data;
      y:=s.findless(xu[u]).data;if y=-maxlongint then y:=s.findless(maxlongint).data;
      if x=maxlongint then x:=0 else x:=dian[x];
      if y=-maxlongint then y:=0 else y:=dian[y];
      ans:=ans-lca(x,u)-lca(y,u)+lca(x,y);
      s.delete(xu[u]);b[u]:=false;dec(cnt1);
    end else
    begin
      x:=s.findgreaterEqual(xu[u]).data;if x=maxlongint then x:=s.findgreater(-maxlongint).data;
      y:=s.findlessEqual(xu[u]).data;if y=-maxlongint then y:=s.findless(maxlongint).data;
      if x=maxlongint then x:=0 else x:=dian[x];
      if y=-maxlongint then y:=0 else y:=dian[y];
      ans:=ans+lca(x,u)+lca(y,u)-lca(x,y);
      s.insert(xu[u]);b[u]:=true;inc(cnt1);
    end;
    writeln(ans);
  end;
end.


Details

Free Pascal Compiler version 3.0.4+dfsg-23 [2019/11/25] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling answer.code
answer.code(1,6) Fatal: Can't find unit Gset used by Program
Fatal: Compilation aborted
Error: /usr/bin/ppcx64 returned an error exitcode