fork download 
  1. /// vn.spoj.com/problems/LUBENICA/
  2.  
  3. /// sparse table for lca&rmq
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define tag "spoj"
  7. #define maxn 100007
  8. #define maxlog ((int)log2(n)+2)
  9. #define module 0
  10. #define oo 1000000007
  11. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  12. int n,m;
  13. struct neigh{ int ver,wei; };
  14. vector< vector<neigh> > adj;
  15. struct nodeTree
  16. {
  17.     vector<int> par;
  18.     vector<int> emax;
  19.     vector<int> emin;
  20.     int depth;
  21.     void reset()
  22.     {
  23.         par.resize(maxlog,0);
  24.         emax.resize(maxlog,0);
  25.         emin.resize(maxlog,0);
  26.         depth=0;
  27.     }
  28. };
  29.  
  30. #define ances(u,i) infor[(u)].par[i]
  31. #define emax(u,i) infor[(u)].emax[i]
  32. #define emin(u,i) infor[(u)].emin[i]
  33. #define par(u) infor[(u)].par[0]
  34. #define depth(u) infor[(u)].depth
  35.  
  36. vector<nodeTree> infor;
  37.  
  38. void dfs(const int &u,const int &parent,const int &depth,const int &wei)
  39. {
  40.     par(u)=parent;
  41.     emax(u,0)=wei;
  42.     emin(u,0)=wei;
  43.     depth(u)=depth;
  44.     for(const neigh &nei: adj[u])
  45.         if(nei.ver!=par(u))
  46.             dfs(nei.ver,u,depth+1,nei.wei);
  47. }
  48. void dplca(const int &N)
  49. {
  50.     ///dp:
  51.     for(int j=1;1<<j<N;j++)
  52.         for(int i=1;i<=N;i++)
  53.         {
  54.             ances(i,j)=ances(ances(i,j-1),j-1);
  55.             emin(i,j)=min(emin(i,j-1),emin(ances(i,j-1),j-1));
  56.             emax(i,j)=max(emax(i,j-1),emax(ances(i,j-1),j-1));
  57.         }
  58. }
  59. struct query{ int lcanc,emi,ema; };
  60. query lca(int u,int v)
  61. {
  62.     int ema=-oo,emi=+oo;
  63.     if(depth(u)<depth(v)) swap(u,v);
  64.  
  65.     while(depth(u)>depth(v))
  66.     {
  67.         emi=min(emi,emin(u,(int)log2(depth(u)-depth(v))));
  68.         ema=max(ema,emax(u,(int)log2(depth(u)-depth(v))));
  69.         u=ances(u,(int)log2(depth(u)-depth(v)));
  70.     }
  71.     int log=log2(depth(u));
  72.     while(u!=v)
  73.     {
  74.         while(ances(u,log)==ances(v,log) && log) --log;
  75.         emi=min(emi,emin(u,log));
  76.         ema=max(ema,emax(u,log));
  77.         emi=min(emi,emin(v,log));
  78.         ema=max(ema,emax(v,log));
  79.         u=ances(u,log),v=ances(v,log);
  80.     }
  81.     return {u,emi,ema};
  82. }
  83. int main()
  84. {
  85.     #ifdef dmdd
  86.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  87.     #endif // dmdd
  88.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  89.     cin>>n;
  90.  
  91.     adj.resize(n+1);
  92.     int x,y,z;
  93.     for(int i=1;i<n;i++)
  94.         cin>>x>>y>>z,adj[x].push_back({y,z}),adj[y].push_back({x,z});
  95.  
  96.     infor.resize(n+1);
  97.     for(int i=0;i<=n;i++) infor[i].reset();
  98.  
  99.     dfs(1,0,1,0);
  100.     dplca(n);
  101.  
  102.     cin>>m;
  103.     query res;
  104.     while(m-->0)
  105.     {
  106.         cin>>x>>y;
  107.         res=lca(x,y);
  108.         cout<<res.emi<<" "<<res.ema<<"\n";
  109.     }
  110.  
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3
stdout 
1 2
2 4
1 5
2 2
1 4
https://ideone.com/t1HEtm
language:
C++14 (gcc 8.3)
created:
6 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!