fork download 
  1. //NETWRKNB
  2. USES Math;
  3. CONST
  4.     tfi = '';
  5.     tfo = '';
  6. TYPE
  7.     node = record
  8.         u,v,k,c,pos,pa: longint;
  9.     end;
  10.     arr = array[0..100000] of node;
  11. VAR
  12.     fi,fo                           : text;
  13.     n,m,cnt,res,jmax,t1,t2          : longint;
  14.     ke,next,ts                      : array[-100000..100000] of longint;
  15.     head,free,tin,tout,ans          : array[0..100000] of longint;
  16.     p,q1,q2,pp                      : arr;
  17.     f                               : array[0..100000,0..20] of longint;
  18.     t,tt                            : array[0..400000] of longint;
  19.  
  20. Procedure add(i,u,v,c: longint);
  21.     Begin
  22.         ke[i]:=v;
  23.         next[i]:=head[u];
  24.         head[u]:=i;
  25.         ts[i]:=c;
  26.     End;
  27.  
  28. Procedure inp;
  29.     Var
  30.         i: longint;
  31.     Begin
  32.         Read(fi,n,m);
  33.         For i:=1 to n-1 do
  34.             with p[i] do
  35.                 begin
  36.                     read(fi,u,v,c);
  37.                     add(i,u,v,c);
  38.                     add(-i,v,u,c);
  39.                 end;
  40.         Readln(fi);
  41.         jmax:=trunc(ln(n)/ln(2));
  42.     End;
  43.  
  44. Procedure dfs(u: longint);
  45.     Var
  46.         j,v: longint;
  47.     Begin
  48.         inc(cnt);
  49.         tin[u]:=cnt;
  50.         j:=1;
  51.         While f[u,j-1]<>0 do
  52.             begin
  53.                 f[u,j]:=f[f[u,j-1],j-1];
  54.                 inc(j);
  55.             end;
  56.         j:=head[u];
  57.         While j<>0 do
  58.             begin
  59.                 v:=ke[j];
  60.                 If tin[v]=0 then
  61.                     begin
  62.                         f[v,0]:=u;
  63.                         dfs(v);
  64.                     end;
  65.                 j:=next[j];
  66.             end;
  67.         tout[u]:=cnt;
  68.     End;
  69.  
  70. Function check(u,v: longint): boolean;
  71.     Begin
  72.         exit((tin[u]<=tin[v]) and (tout[u]>=tout[v]));
  73.     End;
  74.  
  75. Function lca(u,v: longint): longint;
  76.     Var
  77.         j: longint;
  78.     Begin
  79.         If check(u,v) then exit(u);
  80.         If check(v,u) then exit(v);
  81.         For j:=jmax downto 0 do
  82.             If (f[u,j]<>0) and not check(f[u,j],v) then u:=f[u,j];
  83.         exit(f[u,0]);
  84.     End;
  85.  
  86. Procedure swap(var x,y: node);
  87.     Var
  88.         tg: node;
  89.     Begin
  90.         tg:=x; x:=y; y:=tg;
  91.     End;
  92.  
  93. Procedure qsort(l,r: longint; var a: arr);
  94.     Var
  95.         i,j,mid,key: longint;
  96.     Begin
  97.         i:=l;
  98.         j:=r;
  99.         mid:=l+random(r-l+1);
  100.         key:=a[mid].c;
  101.         Repeat
  102.             While a[i].c<key do inc(i);
  103.             While a[j].c>key do dec(j);
  104.             If i<=j then
  105.                 begin
  106.                     swap(a[i],a[j]);
  107.                     inc(i);
  108.                     dec(j);
  109.                 end;
  110.         Until i>j;
  111.         If i<r then qsort(i,r,a);
  112.         If l<j then qsort(l,j,a);
  113.     End;
  114.  
  115. Procedure init;
  116.     Var
  117.         i,tg: longint;
  118.         ch: char;
  119.     Begin
  120.         dfs(1);
  121.         t1:=0; t2:=0;
  122.         For i:=1 to m do
  123.             begin
  124.                 read(fi,ch);
  125.                 If ch='P' then
  126.                     begin
  127.                         inc(t1);
  128.                         with q1[t1] do
  129.                             begin
  130.                                 read(fi,u,v,c);
  131.                                 pos:=i;
  132.                             end;
  133.                     end
  134.                 else
  135.                     begin
  136.                         inc(t2);
  137.                         with q2[t2] do
  138.                             begin
  139.                                 read(fi,k,c);
  140.                                 pos:=i;
  141.                             end;
  142.                     end;
  143.                 readln(fi);
  144.             end;
  145.         For i:=1 to n-1 do pp[i]:=p[i];
  146.         qsort(1,n-1,pp);
  147.         qsort(1,t1,q1);
  148.         qsort(1,t2,q2);
  149.         For i:=1 to n-1 do
  150.             with pp[i] do
  151.                 If check(v,u) then
  152.                     begin
  153.                         tg:=u; u:=v; v:=tg;
  154.                     end;
  155.     End;
  156.  
  157. Procedure new(i,con1,con2: longint);
  158.     Begin
  159.         inc(tt[con1],tt[i]);
  160.         inc(tt[con2],tt[i]);
  161.         inc(t[con1],tt[i]);
  162.         inc(t[con2],tt[i]);
  163.         tt[i]:=0;
  164.     End;
  165. Procedure update(i,l,r,u,v: longint);
  166.     Var
  167.         mid: longint;
  168.     Begin
  169.         If (l=u) and (v=r) then
  170.             begin
  171.                 inc(tt[i]);
  172.                 inc(t[i]);
  173.                 exit;
  174.             end;
  175.         If (r<u) or (v<l) then exit;
  176.         mid:=(l+r) div 2;
  177.         new(i,2*i,2*i+1);
  178.         update(2*i,l,mid,u,min(v,mid));
  179.         update(2*i+1,mid+1,r,max(mid+1,u),v);
  180.         t[i]:=t[2*i]+t[2*i+1];
  181.     End;
  182.  
  183. Function get(i,l,r,u,v: longint): longint;
  184.     Var
  185.         mid: longint;
  186.     Begin
  187.         If (l=u) and (v=r) then exit(t[i]);
  188.         If (r<u) or (v<l) then exit(0);
  189.         mid:=(l+r) div 2;
  190.         new(i,2*i,2*i+1);
  191.         exit(get(2*i,l,mid,u,min(mid,v))+get(2*i+1,mid+1,r,max(mid+1,u),v));
  192.     End;
  193.  
  194. Procedure query1;
  195.     Var
  196.         i,j: longint;
  197.     Begin
  198.         For i:=1 to t1 do
  199.             with q1[i] do pa:=lca(u,v);
  200.         j:=1;
  201.         For i:=1 to t1 do
  202.             with q1[i] do
  203.                 begin
  204.                     While (j<=n-1) and (pp[j].c<=c) do
  205.                         begin
  206.                             with pp[j] do update(1,1,n,tin[v],tout[v]);
  207.                             inc(j);
  208.                         end;
  209.                     ans[pos]:=get(1,1,n,tin[u],tin[u])+get(1,1,n,tin[v],tin[v])-get(1,1,n,tin[pa],tin[pa])*2;
  210.                 end;
  211.     End;
  212.  
  213. Procedure query2;
  214.     Var
  215.         i,j,tmp: longint;
  216.     Begin
  217.         For i:=1 to n*4 do
  218.             begin
  219.                 t[i]:=0; tt[i]:=0;
  220.             end;
  221.         j:=1;
  222.         For i:=1 to t2 do
  223.             with q2[i] do
  224.                 begin
  225.                     While (j<=n-1) and (pp[j].c<=c) do
  226.                         begin
  227.                             with pp[j] do update(1,1,n,tin[u],tin[u]);
  228.                             inc(j);
  229.                         end;
  230.                     with p[k] do
  231.                         If check(u,v) then tmp:=get(1,1,n,tin[v],tout[v])
  232.                         else
  233.                             begin
  234.                                 tmp:=get(1,1,n,1,n)-get(1,1,n,tin[u],tout[u]);
  235.                                 If c<=q2[i].c then dec(res);
  236.                             end;
  237.                     ans[pos]:=tmp;
  238.                 end;
  239.     End;
  240.  
  241. Procedure process;
  242.     Var
  243.         i: longint;
  244.     Begin
  245.         query1;
  246.         query2;
  247.         For i:=1 to m do writeln(fo,ans[i]);
  248.     End;
  249.  
  250. BEGIN
  251.     assign(fi,tfi); reset(fi);
  252.     assign(fo,tfo); rewrite(fo);
  253.         inp;
  254.         init;
  255.         process;
  256.     close(fi); close(fo);
  257. END.
  258.  
Runtime error #stdin #stdout 0s 25528KB
comments (?)
stdin 
Standard input is empty
stdout 
An unhandled exception occurred at $080481D3 :
EDivByZero : Division by zero
  $080481D3
https://ideone.com/00UNwq
PREVOI 2013-2014
language:
Pascal (fpc 3.0.4)
created:
7 years ago
visibility:
public

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!