fork download
copy 
  1. /* 
  2.  Date - 15/9/18
  3.  Kishore P
  4.  Problem :- SPOJ - QTREE
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int maxn=10004;
  9. int ptr,chain_no;
  10.  
  11. vector<int> v[maxn],edg_cost[maxn],index1[maxn];
  12. int par[maxn][14],depth[maxn],sub[maxn];
  13.  
  14. int chain_head[maxn],other_end[maxn],chain_ind[maxn];
  15. int pos_in_arr[maxn],arr[maxn],seg[maxn];
  16.  
  17. // ----------------------------- DFS and LCA -----------------------------------//
  18. void dfs(int s,int frm,int d)
  19. {
  20.  depth[s]=d;     
  21.  par[s][0]=frm;
  22.  sub[s]=1;
  23.  
  24.  int i,ind;
  25.  
  26.  for(i=1;par[s][i-1]!=-1;i++)
  27.  par[s][i]=par[par[s][i-1]][i-1];
  28.  
  29.  for(i=0;i<(int)v[s].size();i++)
  30.  {
  31.     ind=v[s][i]; 
  32.  
  33.     if(ind!=frm)
  34.     {
  35.      other_end[index1[s][i]]=ind;    
  36.      dfs(ind,s,d+1);   
  37.      sub[s]+=sub[ind];
  38.     }
  39.  }
  40.  
  41. }
  42.  
  43. int lca(int x,int y)
  44. {
  45.   if(depth[y] > depth[x])
  46.    swap(x,y);
  47.  
  48.   int i;
  49.   for(i=13;i>=0;i--)
  50.   {if(par[x][i]!=-1 && (depth[par[x][i]] >= depth[y]))
  51.   x=par[x][i];
  52.   }
  53.   if(x==y)
  54.   return x;
  55.  
  56.   for(i=13;i>=0;i--)
  57.   {
  58.     if(par[x][i]!=par[y][i])
  59.     {
  60.      x=par[x][i];
  61.      y=par[y][i];
  62.     }
  63.   }
  64.   return par[x][0];
  65. }
  66.  
  67.  
  68. // ---------------------SEGMENT TREE OPERATIONS ---------------- //
  69.  
  70. void build_seg(int low,int high,int pos)
  71. {
  72.   if(low==high)    
  73.    {
  74.       seg[pos]=arr[low];
  75.       return;
  76.    }    
  77.  
  78.   int mid=(low+high)>>1;
  79.  
  80.   build_seg(low,mid,2*pos+1);
  81.   build_seg(mid+1,high,2*pos+2);
  82.   seg[pos]=(seg[2*pos+1]>seg[2*pos+2])?seg[2*pos+1]:seg[2*pos+2];
  83. }
  84.  
  85. void update_seg(int low,int high,int pos,int ind,int val)
  86. {
  87.  if(low==high)
  88.  {
  89.   seg[pos]=val;
  90.   return ;
  91.  }
  92.  
  93.  int mid=(low+high)>>1;
  94.  
  95.  if(ind<=mid)
  96.  update_seg(low,mid,2*pos+1,ind,val);
  97.  else
  98.  update_seg(mid+1,high,2*pos+2,ind,val);
  99.  
  100.  seg[pos]=(seg[2*pos+1]>seg[2*pos+2])?seg[2*pos+1]:seg[2*pos+2];
  101. }
  102.  
  103. int query_seg(int low,int high,int qlow,int qhigh,int pos)
  104. {
  105.  
  106.   if(high<qlow || qhigh<low)
  107.   return 0;
  108.  
  109.   else if(qlow<=low && high<=qhigh)       
  110.   return seg[pos];    
  111.  
  112.   int mid=(low+high)>>1;
  113.   int l=query_seg(low,mid,qlow,qhigh,2*pos+1);
  114.   int r=query_seg(mid+1,high,qlow,qhigh,2*pos+2);
  115.  
  116.   return (l > r? l : r);
  117. }
  118.  
  119. // --------------------------- Heavy_light Decomposition Building -------------------------------//
  120.  
  121. void HLD(int curr,int prev,int cost)
  122. {
  123.   if(chain_head[chain_no]==-1)
  124.   {
  125.    chain_head[chain_no]=curr;
  126.   }
  127.  
  128.   chain_ind[curr]=chain_no;
  129.   ++ptr;
  130.   pos_in_arr[curr]=ptr;
  131.   arr[ptr]=cost;    
  132.  
  133.   int i,ind,mxid=-1,ncost;
  134.  
  135.   for(i=0;i<(int)v[curr].size();i++) 
  136.   {
  137.     ind=v[curr][i];  
  138.     if(ind!=prev)
  139.     {
  140.       if(mxid==-1 || (sub[ind] > sub[mxid]))
  141.       {
  142.        mxid=ind;
  143.        ncost=edg_cost[curr][i];
  144.       }
  145.     }
  146.   }
  147.  
  148.   if(mxid!=-1)
  149.   {
  150.    HLD(mxid,curr,ncost);
  151.   }
  152.  
  153.   for(i=0;i<(int)v[curr].size();i++)
  154.   {
  155.    ind=v[curr][i];    
  156.    if(ind!=prev)
  157.    {
  158.      if(ind!=mxid)
  159.      {
  160.       chain_no++;
  161.       HLD(ind,curr,edg_cost[curr][i]);
  162.      }
  163.    }
  164.   }
  165. }
  166.  
  167. //------------------------- Using HLD to answer queries and updates ---------------------//
  168.  
  169. void update(int num,int val)
  170. {
  171.  int x=other_end[num];
  172.  update_seg(0,ptr,0,pos_in_arr[x],val);
  173. }
  174.  
  175. int query_up(int x,int y) // y is ancestor of x
  176. {
  177.   if(x==y)
  178.   return 0;
  179.  
  180.   int xchain,ychain=chain_ind[y],ans=0,temp;
  181.  
  182.   while(1)
  183.   {
  184.     xchain=chain_ind[x];
  185.  
  186.     if(xchain==ychain)
  187.     {
  188.       if(x==y)
  189.       break;
  190.  
  191.      temp=query_seg(0,ptr,pos_in_arr[y]+1,pos_in_arr[x],0);
  192.      if(temp > ans)
  193.      ans=temp;
  194.      break;
  195.     }
  196.  
  197.     int head=chain_head[xchain];
  198.     temp=query_seg(0,ptr,pos_in_arr[head],pos_in_arr[x],0);
  199.  
  200.     if(temp > ans)
  201.     ans=temp;
  202.     x=par[head][0]; 
  203.   }
  204.  return ans;    
  205. }
  206.  
  207. int query(int x,int y)
  208. {
  209.    int L=lca(x,y);   
  210.  
  211.    int ans1=query_up(x,L);
  212.    int ans2=query_up(y,L);
  213.  
  214.    return ((ans1>ans2)?ans1:ans2);    
  215. }
  216.  
  217. //------------------------------------------------------------------------------------
  218.  
  219. int main()
  220. {
  221.    int t;
  222.    scanf("%d",&t);
  223.  
  224.    while(t--)
  225.    {
  226.     int n;
  227.     scanf("%d",&n);
  228.  
  229.     int i,j,a,b,c;
  230.  
  231.     for(i=0;i<=n;i++)
  232.     {
  233.       v[i].clear();
  234.       edg_cost[i].clear();
  235.       index1[i].clear();
  236.  
  237.       chain_head[i]=-1;
  238.  
  239.       for(j=0;j<14;j++)
  240.       par[i][j]=-1;
  241.     }
  242.  
  243.     for(i=1;i<n;i++)
  244.     {
  245.      scanf("%d %d %d",&a,&b,&c);
  246.  
  247.      v[a].push_back(b);
  248.      v[b].push_back(a);
  249.  
  250.      edg_cost[a].push_back(c);
  251.      edg_cost[b].push_back(c);
  252.  
  253.      index1[a].push_back(i);
  254.      index1[b].push_back(i);
  255.     }
  256.  
  257.     dfs(1,-1,0);
  258.  
  259.     ptr=-1;chain_no=0;
  260.     HLD(1,-1,0); // (root,frm,cost)  
  261.     build_seg(0,ptr,0);
  262.  
  263.     while(1)
  264.     {
  265.      char s[100];
  266.      scanf("%s",s);
  267.  
  268.      if(s[0]=='D')
  269.      break;
  270.  
  271.       if(s[0]=='Q')
  272.      {
  273.       scanf("%d %d",&a,&b);
  274.       printf("%d\n",query(a,b));
  275.      }
  276.  
  277.      else
  278.      {
  279.       scanf("%d %d",&a,&c);
  280.       update(a,c);
  281.      }
  282.  
  283.     }
  284.  
  285.    }    
  286.  
  287.     return 0;
  288. }
Success #stdin #stdout 0s 16800KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/nY5ov4
heavy ligth decomp ,, Spoj - qtree fronm anudeep blog
language:
C++14 (gcc 8.3)
created:
5 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!