fork download 
  1.  
  2.     const fi='network.inp';
  3.           fo='network.out';
  4.             maxn=round(1e5)*2;
  5.             maxn1=round(1e6)*5;
  6.  
  7.     var w,a,h,p,x,y,z,u,v,c,cs,tt,con,nhan,d,loai,nhancuadinh:array[0..maxn]of longint;
  8.         it2,it,lazy:array[0..maxn1]of longint;
  9.         b:array[0..round(1e5),0..20]of longint;
  10.         n,m,slnhan,top:longint;
  11.     procedure mo;
  12.         begin
  13.             assign(input,fi);reset(input);
  14.             assign(output,fo);rewrite(output);
  15.         end;
  16.  
  17.     procedure dong;
  18.         begin
  19.             closE(input);closE(output);
  20.         end;
  21.  
  22.     procedure nhap;
  23.         var i,k:longint;
  24.             xx:char;
  25.             begin
  26.                 readln(n,m);
  27.                 for i:=1 to n-1 do
  28.                     begin
  29.                         readln(X[i],y[i],z[i]);
  30.                         inc(h[x[i]]);
  31.                         inc(h[y[i]]);
  32.                     end;
  33.                 for i:=1 to n+1 do inc(h[i],h[i-1]);
  34.                 for i:=1 to n-1 do
  35.                     begin
  36.                         a[h[x[i]]]:=y[i];
  37.                         p[h[x[i]]]:=z[i];
  38.                         dec(h[x[i]]);
  39.                         a[h[y[i]]]:=x[i];
  40.                         p[h[y[i]]]:=z[i];
  41.                         dec(h[y[i]]);
  42.                     end;
  43.  
  44.                 for i:=1 to m do
  45.                     begin
  46.                         read(xx);
  47.                         if xx='P' then
  48.                             begin
  49.                             readln(u[i],v[i],c[i]);
  50.                             loai[i]:=1;
  51.                             end
  52.                         else
  53.                             begin
  54.                                 readln(k,c[i]);
  55.                                 u[i]:=x[k];
  56.                                 v[i]:=y[k];
  57.                                 loai[i]:=2;
  58.                             end;
  59.                     end;
  60.             end;
  61.  
  62.     procedure swap(var i,j:longint);
  63.         var t:longint;
  64.             begin
  65.                 t:=i;
  66.                 i:=j;
  67.                 j:=t;
  68.             end;
  69.  
  70.     procedure qs(l,r:longint);
  71.         var x,i,j:longint;
  72.             begin
  73.                 i:=l;
  74.                 j:=r;
  75.                 x:=w[random(r-l)+1+l];
  76.                 repeat
  77.                     while w[i]<x do inc(i);
  78.                     while x<w[j] do dec(j);
  79.                     if i<=j then
  80.                         begin
  81.                             swap(cs[i],cs[j]);
  82.                             swap(w[i],w[j]);
  83.                             inc(i);
  84.                             dec(j);
  85.                         end;
  86.                 until i>j;
  87.                 if i<r then qs(i,r);
  88.                 if l<j then qs(l,j);
  89.             end;
  90.  
  91.     procedure qstv(l,r:longint);
  92.         var x,i,j:longint;
  93.             begin
  94.                 i:=l;
  95.                 j:=r;
  96.                 x:=c[random(r-l)+1+l];
  97.                 repeat
  98.                     while (c[i]<x) do inc(i);
  99.                     while (x<c[j]) do dec(j);
  100.                     if i<=j then
  101.                         begin
  102.                             swap(c[i],c[j]);
  103.                             swap(u[i],u[j]);
  104.                             swap(v[i],v[j]);
  105.                             swap(tt[i],tt[j]);
  106.                             swap(loai[i],loai[j]);
  107.                             inc(i);
  108.                             dec(j);
  109.                         end;
  110.                 until i>j;
  111.                 if i<r then qstv(i,r);
  112.                 if l<j then qstv(l,j);
  113.             end;
  114.  
  115.     procedure dfs(u:longint);
  116.         var v:longint;
  117.             begin
  118.                 con[u]:=1;
  119.                 for v:=h[u]+1 to h[u+1] do
  120.                     if nhan[a[v]]=0 then
  121.                         begin
  122.                             w[a[v]]:=p[v];
  123.                             b[a[v],0]:=u;
  124.                             d[a[v]]:=d[u]+1;
  125.                             inc(slnhan);
  126.                             nhan[a[v]]:=slnhan;
  127.                             dfs(a[v]);
  128.                             con[u]:=con[a[v]]+con[u];
  129.                         end;
  130.             end;
  131.  
  132.     procedure sort;
  133.         var i:longint;
  134.             begin
  135.                 slnhan:=1;
  136.                 nhan[1]:=1;
  137.                 d[1]:=1;
  138.                 dfs(1);
  139.                 //for i:=1 to n do
  140.                 //    writeln(nhan[i],' ',con[i]);
  141.                 for i:=1 to n do cs[i]:=i;
  142.                 qs(1,n);
  143.                 //for i:=1 to n do writeln(cs[i],' ',w[i]);
  144.                 for i:=1 to m do tt[i]:=i;
  145.                 qstv(1,m);
  146.                 //for i:=1 to m do writeln(u[i],' ',v[i],' ',c[i],' ',tt[i]);
  147.             end;
  148.  
  149.     procedure qsnhan(l,r:longint);
  150.         var i,j,x:longint;
  151.             begin
  152.                 i:=l;
  153.                 j:=r;
  154.                 x:=nhan[random(r-l)+1+l];
  155.                 repeat
  156.                     while nhan[i]<x do inc(i);
  157.                     while x<nhan[j] do dec(j);
  158.                     if i<=j then
  159.                         begin
  160.                             swap(nhan[i],nhan[j]);
  161.                             //swap(nhancuadinh[i],nhancuadinh[j]);
  162.                             inc(i);
  163.                             dec(j);
  164.                         end;
  165.                 until i>j;
  166.                 if i<r then qsnhan(i,r);
  167.                 if l<j then qsnhan(l,j);
  168.             end;
  169.  
  170.         procedure update(u,v,l,r,i:longint);
  171.             var mid:longint;
  172.                 begin
  173.                     it[i]:=it[i]+lazy[i];
  174.                     lazy[i*2]:=lazy[i*2]+lazy[i];
  175.                     lazy[i*2+1]:=lazy[i*2+1]+lazy[i];
  176.                     lazy[i]:=0;
  177.                     if (r<u) or (v<l) then exit;
  178.                     if (u<=l) and (r<=v) then
  179.                         begin
  180.                             it[i]:=it[i]+1;
  181.                             lazy[i]:=0;
  182.                             lazy[i*2]:=lazy[i*2]+1;
  183.                             lazy[i*2+1]:=lazy[i*2+1]+1;
  184.                             exit;
  185.                         end;
  186.                     mid:=(l+r) div 2;
  187.                     update(u,v,l,mid,i*2);
  188.                     update(u,v,mid+1,r,i*2+1);
  189.                     //it[i]:=it[i*2]+it[i*2+1];
  190.                 end;
  191.  
  192.         function find(u,l,r,i:longint):longint;
  193.             var mid:longint;
  194.                 begin
  195.                     it[i]:=it[i]+lazy[i];
  196.                     lazy[i*2]:=lazy[i*2]+lazy[i];
  197.                     lazy[i*2+1]:=lazy[i*2+1]+lazy[i];
  198.                     lazy[i]:=0;
  199.                     if (r<u) or (u<l) then exit(0);
  200.                     if (l=u) and (l=r) then exit(it[i]);
  201.                     mid:=(l+r) div 2;
  202.                     exit(find(u,l,mid,i*2)+find(u,mid+1,r,i*2+1));
  203.                 end;
  204.  
  205.         procedure rmq;
  206.             var i,j:longint;
  207.                 begin
  208.                     for j:=1 to 20 do
  209.                         for i:=1 to n do
  210.                             b[i,j]:=b[b[i,j-1],j-1];
  211.                 end;
  212.  
  213.         function lca(u,v:longint):longint;
  214.             var k,i,res:longint;
  215.                 begin
  216.                     if d[u]>=d[v] then
  217.                         begin
  218.                             k:=d[u]-d[v];
  219.                             if k>0 then
  220.                                 for i:=20 downto 0 do
  221.                                     if k>=1 shl i then
  222.                                         begin
  223.                                             k:=k-1 shl i;
  224.                                             u:=b[u,i];
  225.                                         end;
  226.                             if u=v then exit(u);
  227.                             for i:=20 downto 0 do
  228.                                 if b[u,i]=b[v,i] then res:=b[u,i] else
  229.                                     begin
  230.                                         u:=b[u,i];
  231.                                         v:=b[v,i];
  232.                                     end;
  233.                             exit(res);
  234.                         end
  235.                     else exit(lca(v,u));
  236.                 end;
  237.  
  238.         procedure push(xx,tt:longint);
  239.             begin
  240.                 inc(top);
  241.                 x[top]:=xx;
  242.                 y[top]:=tt;
  243.             end;
  244.  
  245.         procedure update2(u,l,r,i:longint);
  246.             var mid:longint;
  247.                 begin
  248.                     if (r<u) or (u<l) then exit;
  249.                     if (l=r) and (l=u) then
  250.                         begin
  251.                             it2[i]:=1;
  252.                             exit;
  253.                         end;
  254.                     mid:=(l+r) div 2;
  255.                     update2(u,l,mid,i*2);
  256.                     update2(u,mid+1,r,i*2+1);
  257.                     it2[i]:=it2[i*2]+it2[i*2+1];
  258.                 end;
  259.         function find2(u,v,l,r,i:longint):longint;
  260.             var mid:longint;
  261.                 begin
  262.                     if (r<u) or (v<l) then exit(0);
  263.                     if (u<=l) and (r<=v) then exit(it2[i]);
  264.                     mid:=(l+r) div 2;
  265.                     exit(find2(u,v,l,mid,i*2)+find2(u,v,mid+1,r,i*2+1));
  266.                 end;
  267.  
  268.         function min(a,b:longint):longint;
  269.             begin
  270.                 if a<b  then exit(a) else exit(b);
  271.             end;
  272.  
  273.         procedure truyvan;
  274.         var jj,t,i,j,resu,resc,resv,chung:longint;
  275.             begin
  276.                     rmq;
  277.                     for i:=1 to n do nhancuadinh[i]:=nhan[i];
  278.                     qsnhan(1,n);
  279.                     j:=0;
  280.                     for i:=1 to m do
  281.                         begin
  282.                             while (c[i]>=w[j+1])and (j<n) do
  283.                                 begin
  284.                                 inc(j);
  285.                                 update(nhancuadinh[cs[j]],nhancuadinh[cs[j]]+con[cs[j]]-1,1,n,1);
  286.                                 update2(nhancuadinh[cs[j]],1,n,1);
  287.                                 //writeln(nhancuadinh[cs[j]],' ',nhancuadinh[cs[j]]+con[cs[j]]-1);
  288.                                 {for jj:=1 to n do
  289.                                     begin
  290.                                     t:=(find(jj,1,maxn1,1));
  291.                                     writeln(t);
  292.                                     end; }
  293.                                 end;
  294.                             if loai[i]=1 then
  295.                                 begin
  296.                                     chung:=lca(u[i],v[i]);
  297.                                     resu:=find(nhancuadinh[u[i]],1,n,1);
  298.                                     resv:=find(nhancuadinh[v[i]],1,n,1);
  299.                                     resc:=find(nhancuadinh[chung],1,n,1);
  300.                                     push(resu+resv-2*resc,tt[i]);
  301.                                     //writeln(resu,' ',resv,' ',resc,' ',u[i],' ',v[i],' ',c[i],' ',resu+resv-2*resc);
  302.                                     //writeln(resu+resv-2*resc);
  303.                                 end
  304.                             else
  305.                                 begin
  306.                                     if b[v[i],0]=u[i] then
  307.                                         begin
  308.                                             t:=find2(nhancuadinh[v[i]]+1,nhancuadinh[v[i]]+con[v[i]]-1,1,n,1);
  309.                                             push(t,tt[i]);
  310.                                             //writeln(t,' ',u[i],' ',v[i],' ',j);
  311.                                             //writeln(t);
  312.                                             //for jj:=1 to n do
  313.                                             //    begin
  314.                                             //        writeln(find2(nhancuadinh[jj]+1,nhancuadinh[jj]+con[jj]-1,1,maxn,1),' dinh ',jj);
  315.                                             //    end;
  316.                                         end
  317.                                     else
  318.                                         begin
  319.                                             push(find2(nhancuadinh[u[i]]+1,nhancuadinh[u[i]]+con[u[i]]-1,1,n,1),tt[i]);
  320.                                             //writeln(find(v[i],1,maxn1,1)-1);
  321.                                         end;
  322.                                 end;
  323.                             //writeln(tt[i],' ',x[i]);
  324.                         end;
  325.             end;
  326.  
  327.     procedure qskq(l,r:longint);
  328.         var i,j,xx:longint;
  329.             begin
  330.                 i:=l;
  331.                 j:=r;
  332.                 xx:=y[random(r-l)+1+l];
  333.                 repeat
  334.                     while y[i]<xx do inc(i);
  335.                     while xx<y[j] do dec(j);
  336.                     if i<=j then
  337.                         begin
  338.                             swap(x[i],x[j]);
  339.                             swap(y[i],y[j]);
  340.                             dec(j);
  341.                             inc(i);
  342.                         end;
  343.                 until i>j;
  344.                 if i<r then qskq(i,r);
  345.                 if l<j then qskq(l,j);
  346.             end;
  347.  
  348.     procedure xuat;
  349.         var i:longint;
  350.             begin
  351.                 qskq(1,top);
  352.                 for i:=1 to top do writeln(x[i]);
  353.                 //for i:=1 to n do writeln(find(1,1,maxn1,1));
  354.             end;
  355.  
  356. begin
  357.         mo;
  358.         nhap;
  359.         sort;
  360.         truyvan;
  361.         xuat;
  362.         dong;
  363.     end.
  364.  
  365.  
Runtime error #stdin #stdout 0s 80384KB
comments (?)
stdin 
Standard input is empty
stdout 
Runtime error 2 at $080480E4
  $080480E4
https://ideone.com/Csui7X
language:
Pascal (fpc 3.0.4)
created:
9 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!