Advertisement
ismaeil

Algo pro log n 2

Jul 24th, 2020
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> ii;
  5. const int N = 1e5 + 5e1;
  6. #define rg (p << 1) | 1
  7. #define lf (p << 1)
  8. #define OO INT_MAX
  9. #define S second
  10. #define F first
  11.  
  12. int Tree[N][2] ,idx[N] ,ListNum[N];
  13. vector< vector <int > > TreeList;
  14. vector< int > Tmp;
  15. int n ,Q;
  16.  
  17. int DfsSpTree[N * 2][2]; /// DFS Spanning Tree
  18. int DfsSize = 1;    /// DFS Spanning Tree Size
  19.  
  20. class SegTree {
  21.     private:
  22.             vector< ii > Seg;
  23.  
  24.             ii Compain(ii a ,ii b) {
  25.                     return (a.S < b.S) ? a : b;
  26.             }
  27.  
  28.             void Build(int p ,int L ,int R){
  29.                     if( L == R ) {
  30.                             Seg[p] = ii( DfsSpTree[L][0] ,DfsSpTree[L][1] );
  31.                             return;
  32.                     }
  33.  
  34.                     int Mid = (L + R) >> 1;
  35.                     Build(lf ,L ,Mid);
  36.                     Build(rg ,Mid + 1 ,R);
  37.                     Seg[p] = Compain(Seg[lf] ,Seg[rg]);
  38.             }
  39.  
  40.             ii QRY(int i ,int j ,int p ,int L ,int R){
  41.                     if( i >  R || L >  j ) return ii(OO ,OO);
  42.                     if( i <= L && R <= j ) return Seg[p];
  43.  
  44.                     int Mid = (L + R) >> 1;
  45.                     ii LF  = QRY(i ,j ,lf ,L ,Mid);
  46.                     ii RG  = QRY(i ,j ,rg ,Mid + 1 ,R);
  47.                     return Compain(LF ,RG);
  48.             }
  49.  
  50.     public:
  51.             void Build() {
  52.                     Build(1 ,1 ,DfsSize - 1);
  53.             }
  54.             void ReSize(int n) {
  55.                     Seg.assign(n * 4 ,ii(0,OO));
  56.             }
  57.             ii QRY(int L ,int R) {
  58.                     return QRY(L ,R ,1 ,1 ,DfsSize - 1);
  59.             }
  60. } ST ;
  61.  
  62. void Dfs_Pre_Order(int u = 1 ,int Depth = 1) {
  63.         DfsSpTree[ DfsSize ][0] = u;
  64.         DfsSpTree[ DfsSize ][1] = Depth;
  65.         Tmp.push_back(u);
  66.  
  67.         ListNum[u] = (int)TreeList.size();
  68.         idx[u] = DfsSize;
  69.         DfsSize ++;
  70.  
  71.         bool NodeIsLeaf = true;
  72.         for(int j = 0 ; j < 2 ; j++){
  73.                 int v = Tree[u][j];
  74.                 if( v != -1 ){
  75.                         NodeIsLeaf = false;
  76.                         Dfs_Pre_Order(v ,Depth + 1);
  77.                         DfsSpTree[ DfsSize ][0] = u;
  78.                         DfsSpTree[ DfsSize ][1] = Depth;
  79.                         DfsSize++;
  80.                 }
  81.         }
  82.         if( NodeIsLeaf ) TreeList.push_back( Tmp );
  83.         Tmp.pop_back();
  84. }
  85.  
  86. void Memset(int n) {
  87.     for(int i = 0 ; i <= n ; i++)
  88.             idx[i] = ListNum[i] = -1;
  89. }
  90. /// ------------------------------------------------------------------ ///
  91.  
  92. void SolveQuery(){
  93.         int u ,v;
  94.         scanf("%d%d" ,&u ,&v);
  95.  
  96.         int L = idx[u] ,R = idx[v];
  97.         if( L > R )swap(L ,R);
  98.         ii Ancestor = ST.QRY(L ,R);
  99.  
  100.         int AncHigh = DfsSpTree[ idx[Ancestor.F] ][1] ,
  101.             Uhigh   = DfsSpTree[ idx[u] ][1],
  102.             Vhigh   = DfsSpTree[ idx[v] ][1];
  103.  
  104.         int Ans = -1;
  105.         if( Uhigh == Vhigh )
  106.                 Ans = Ancestor.F;
  107.         else if( Uhigh > Vhigh ) {
  108.                 int NumOfList = ListNum[u];
  109.                 int Diff = Vhigh - AncHigh;
  110.                 int Mid  = (AncHigh + Uhigh - Diff) >> 1;
  111.                 Ans = TreeList[ NumOfList ][ Mid - 1 ];
  112.         }
  113.         else if( Uhigh < Vhigh ) {
  114.                 int NumOfList = ListNum[v];
  115.                 int Diff = Uhigh - AncHigh;
  116.                 int Mid = (AncHigh + Vhigh - Diff) >> 1;
  117.                 Ans = TreeList[ NumOfList ][ Mid - 1 ];
  118.         }
  119.  
  120.         printf("%d\n" ,Ans);
  121. }
  122.  
  123. int main() {
  124.         scanf("%d" ,&n);
  125.         for(int i=1 ; i <= n ; i++) {
  126.                 int L ,R; scanf("%d%d" ,&L ,&R);
  127.                 Tree[i][0] = L;
  128.                 Tree[i][1] = R;
  129.         }
  130.  
  131.         Memset(n + 1);
  132.         Dfs_Pre_Order();
  133.  
  134.         ST.ReSize(DfsSize + 1);
  135.         ST.Build();
  136.  
  137.         scanf("%d" ,&Q);
  138.         while( Q-- ) SolveQuery();
  139.     return 0;
  140. }
  141.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement