fork download
copy 
  1.  const fi='bdoi16e.inp';
  2.           fo='bdoi16e.out';
  3.             maxn=200000;
  4.             maxx=1000000;
  5.     var free,bait,res,vitri,l,r,x,y,h,a,trace:array[0..maxn]of longint;
  6.         z,d,p,w:array[0..maxn]of int64;
  7.         it:array[0..maxx]of longint;
  8.             i,goc,ll,n,top,count:longint;
  9.     procedure mo;
  10.         begin
  11.             assign(input,fi);reseT(input);
  12.             assign(output,fo);rewrite(output);
  13.         end;
  14.     procedure dong;
  15.         begin
  16.             close(input);closE(output);
  17.         end;
  18.     procedure dfs(u:longint);
  19.         var v:longint;
  20.             begin
  21.                 inc(count);
  22.                 l[u]:=count;
  23.                 vitri[count]:=u;
  24.                 for v:=h[u]+1 to h[u+1] do
  25.                     if (trace[a[v]]=0) then
  26.                         begin
  27.                             trace[a[v]]:=u;
  28.                             d[a[v]]:=d[u]+p[v];
  29.                             dfs(a[v]);
  30.                         end;
  31.                 r[u]:=count;
  32.             end;
  33.     function search(x:int64):longint;
  34.         var l,r,mid:longint;
  35.             begin
  36.                 l:=1;
  37.                 r:=top;
  38.                 while l<=r do
  39.                     begin
  40.                         mid:=(l+r) div 2;
  41.                         if (w[mid]=x) then exit(mid);
  42.                         if (W[mid]<x) then l:=mid+1 else r:=mid-1;
  43.                     end;
  44.             end;
  45.     procedure qs(l,r:longint);
  46.         var i,j,m:longint;
  47.             x,t:int64;
  48.                 begin
  49.                     i:=l;
  50.                     j:=r;
  51.                     m:=random(r-l)+1+l;
  52.                     x:=w[m];
  53.                     repeat
  54.                         while (w[i]<x) do inc(i);
  55.                         while (x<w[j]) do dec(j);
  56.                         if i<=j then
  57.                             begin
  58.                                 t:=w[i];
  59.                                 w[i]:=w[j];
  60.                                 w[j]:=t;
  61.                                 inc(i);dec(j);
  62.                             end;
  63.                     until i>j;
  64.                     if i<r then qs(i,r);
  65.                     if l<j then qs(l,j);
  66.                 end;
  67.     procedure update(u,w,l,r,i:longint);
  68.         var mid:longint;
  69.             begin
  70.                 if (r<u) or (u<l) then exit;
  71.                 if (u=l) and (u=r) then
  72.                     begin
  73.                         it[i]:=w;
  74.                         exit;
  75.                     end;
  76.                 mid:=(l+r) div 2;
  77.                 update(u,w,l,mid,i*2);
  78.                 update(u,w,mid+1,r,i*2+1);
  79.                 it[i]:=it[i*2]+it[i*2+1];
  80.             end;
  81.     function find(u,v,l,r,i:longint):longint;
  82.         var mid:longint;
  83.             begin
  84.                 if (r<u) or (v<l) then exit(0);
  85.                 if (u<=l) and (r<=v) then exit(it[i]);
  86.                 mid:=(l+r) div 2;
  87.                 exit(find(u,v,l,mid,i*2)+find(u,v,mid+1,r,i*2+1));
  88.             end;
  89.     procedure bfs(u:longint);
  90.         var v:longint;
  91.             begin
  92.                 inc(count);
  93.                 while (ll+1<l[u]) do
  94.                     begin
  95.                         if (trace[ll+1]<n+1) then update(trace[ll+1],1,1,n,1);
  96.                         inc(ll);
  97.                     end;
  98.                 res[u]:=find(l[u],r[u],1,n,1);
  99.                 for v:=h[u]+1 to h[u+1] do
  100.                         bfs(a[v]);
  101.             end;
  102.     procedure nhap;
  103.     var i:longint;
  104.         begin
  105.             readln(n);
  106.             for i:=1 to n do read(W[i]);
  107.             for i:=1 to n do read(x[i]);
  108.             for i:=1 to n do read(z[i]);
  109.             for i:=1 to n do
  110.                 if x[i]=0 then goc:=i else
  111.                     begin
  112.                         y[i]:=i;
  113.                         inc(h[x[i]]);
  114.                     end;
  115.             for i:=1 to n+1 do inc(h[i],h[i-1]);
  116.             for i:=1 to n do
  117.                 if x[i]<>0 then
  118.                     begin
  119.                         a[h[x[i]]]:=y[i];
  120.                         p[h[x[i]]]:=z[i];
  121.                         dec(h[x[i]]);
  122.                     end;
  123.             trace[goc]:=-1;
  124.             count:=0;
  125.             dfs(goc);
  126.             for i:=1 to n do d[i]:=d[i]+w[i];
  127.             for i:=1 to n do w[i]:=d[i];
  128.             qs(1,n);
  129.             top:=1;
  130.             for i:=2 to n do
  131.                 if w[i]<>w[i-1] then
  132.                     begin
  133.                         inc(top);
  134.                         w[top]:=w[i];
  135.                     end;
  136.             for i:=1 to n do d[i]:=search(d[i]);
  137.             for i:=1 to n do bait[i]:=n+1;
  138.             for i:=n downto 1 do
  139.                 begin
  140.                     trace[i]:=bait[d[vitri[i]]];
  141.                     bait[d[vitri[i]]]:=i;
  142.                 end;
  143.             for i:=1 to n do
  144.                 if free[d[vitri[i]]]=0 then
  145.                     begin
  146.                         update(i,1,1,n,1);
  147.                         free[d[vitri[i]]]:=1;
  148.                     end;
  149.             ll:=0;
  150.             count:=0;
  151.         end;
  152.     begin
  153.        // mo;
  154.         nhap;
  155.         bfs(goc);
  156.         for i:=1 to n do writeln(Res[i]);
  157.        // dong;
  158.     end.
  159.  
Success #stdin #stdout 0s 19040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XNRYVr
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!