daily pastebin goal
73%
SHARE
TWEET

Faj nlogn

a guest Mar 26th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Author: Gyeonggeun Kim(kriii)
  3.  * Time Complexity: O(N lg N)
  4.  */
  5. #include <stdio.h>
  6.  
  7. const int Z = 1<<21;
  8.  
  9. int N,M,V,par[Z/2],dist[Z/2],child[Z/2],size[Z/2],st[Z/2],ed[Z/2];
  10. long long my[Z/2];
  11.  
  12. struct node{
  13.     node(){
  14.         x = i = 0;
  15.     }
  16.     node(long long x_, int i_){
  17.         x = x_; i = i_;
  18.     }
  19.     long long x; int i;
  20.  
  21.     bool operator <(const node &t)const{
  22.         return x < t.x;
  23.     };
  24.  
  25.     node operator +(const node &t)const{
  26.         if (x < t.x) return t;
  27.         return (*this);
  28.     }
  29. }I[Z*2];
  30.  
  31. void in(long long x, int i)
  32. {
  33.     I[i+Z] = node(x,i);
  34.     i = (i + Z) >> 1;
  35.     while (i){
  36.         I[i] = I[i*2] + I[i*2+1];
  37.         i >>= 1;
  38.     }
  39. }
  40.  
  41. node out(int i, int j)
  42. {
  43.     node res;
  44.     i += Z; j += Z;
  45.     while (i < j){
  46.         if (i & 1){
  47.             if (res < I[i]) res = I[i];
  48.             i++;
  49.         }
  50.         if (~j & 1){
  51.             if (res < I[j]) res = I[j];
  52.             j--;
  53.         }
  54.         i >>= 1; j >>= 1;
  55.     }
  56.     if (i == j){
  57.         if (res < I[i]) res = I[i];
  58.     }
  59.     return res;
  60. }
  61.  
  62. long long remove(int s, int e)
  63. {
  64.     node t = out(s,e);
  65.     in(0,t.i);
  66.     return t.x;
  67. }
  68.  
  69. int main()
  70. {
  71.     scanf ("%d %d",&N,&M); V = N + M;
  72.  
  73.     for (int i=2;i<=V;i++){
  74.         scanf ("%d %d",&par[i],&dist[i]);
  75.         child[par[i]]++;
  76.     }
  77.  
  78.     for (int i=V;i>=1;i--){
  79.         size[i]++;
  80.         size[par[i]] += size[i];
  81.     }
  82.  
  83.     ed[1] = 1;
  84.     for (int i=2;i<=V;i++){
  85.         st[i] = ed[par[i]] + 1;
  86.         ed[i] = st[i] + 1;
  87.         ed[par[i]] = st[i] + size[i] * 2 - 1;
  88.     }
  89.  
  90.     for (int i=V;i>=2;i--){
  91.         int s = st[i], e = ed[i];
  92.         for (int k=1;k<child[i];k++) my[i] += remove(s,e);
  93.         long long p = remove(s,e);
  94.         long long q = remove(s,e);
  95.         in(dist[i]+p,s);
  96.         in(dist[i]+q,s+1);
  97.         my[i] -= dist[i];
  98.         my[par[i]] += my[i];
  99.     }
  100.  
  101.     for (int k=0;k<child[1];k++) my[1] += remove(st[1],ed[1]);
  102.     printf ("%lld\n",my[1]);
  103.  
  104.     return 0;
  105. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top