ismaeil

Algo pro1 O(NLogN + QLogN)

Jul 30th, 2020 (edited)
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.15 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 OO INT_MAX
  7. #define S second
  8. #define F first
  9.  
  10. int Tree[N][2] ,Par[N] ,idx[N];
  11. int n ,Q;
  12.  
  13. int DfsSpTree[N * 2][2]; /// DFS Spanning Tree
  14. int DfsSize = 1;    /// DFS Spanning Tree Size
  15.  
  16. const int Log = (int)log2(N*2);
  17. ii MinSpTable[N * 2][Log];
  18. int AncOfNodes[N][Log];
  19.  
  20. void Dfs_Pre_Order(int u = 1 ,int Depth = 1) {
  21.         DfsSpTree[ DfsSize ][0] = u;
  22.         DfsSpTree[ DfsSize ][1] = Depth;
  23.  
  24.         idx[u] = DfsSize;
  25.         DfsSize ++;
  26.  
  27.         for(int j = 0 ; j < 2 ; j++){
  28.                 int v = Tree[u][j];
  29.                 if( v != -1 ){
  30.                         Dfs_Pre_Order(v ,Depth + 1);
  31.                         DfsSpTree[ DfsSize ][0] = u;
  32.                         DfsSpTree[ DfsSize ][1] = Depth;
  33.                         DfsSize++;
  34.                 }
  35.         }
  36. }
  37.  
  38. void FillSparseTable(int Size ,int Log) {
  39.         for(int i = 0 ; i <= Size ; i++)
  40.                 for(int j=0 ; j <= Log ; j++)
  41.                         MinSpTable[i][j] = ii(-1 ,OO);
  42.  
  43.         for(int i = 1 ; i < Size  ; i++)
  44.                 MinSpTable[i][0] = ii(DfsSpTree[i][0] , DfsSpTree[i][1]);
  45.         for(int j = 1 ; j <= Log ; j++){
  46.                 int Rang = (1 << j);
  47.                 int Mid  = (Rang >> 1);
  48.                 for(int i = 1 ; i + Rang - 1 < Size ; i++) {
  49.                         if( MinSpTable[i][j - 1].S < MinSpTable[i + Mid][j - 1].S )
  50.                              MinSpTable[i][j] = MinSpTable[i][j - 1];
  51.                         else MinSpTable[i][j] = MinSpTable[i + Mid][j - 1];
  52.                 }
  53.         }
  54. }
  55.  
  56. ii GetAncestor(int L ,int R) {
  57.         int Rang = R - L + 1;
  58.         int K = (int)log2( Rang );
  59.  
  60.         ii Res = ii(OO ,OO);
  61.         if( MinSpTable[L][K].S <= MinSpTable[R - (1 << K) + 1][K].S )
  62.              Res = MinSpTable[L][K];
  63.         else Res = MinSpTable[R - (1 << K) + 1][K];
  64.  
  65.         return Res;
  66. }
  67.  
  68. void FillAncsOfNodes(int n ,int Log) {
  69.         for(int i = 0 ; i <= n ; i++)
  70.                 for(int j=0 ; j <= Log ; j++)
  71.                         AncOfNodes[i][j] = 1;
  72.  
  73.         for(int i = 1 ; i <= n ; i++)
  74.                 AncOfNodes[i][0] = Par[i];
  75.         for(int j = 1 ; j <= Log ; j++)
  76.                 for(int i = 1 ; i <= n ; i++)
  77.                         AncOfNodes[i][j] = AncOfNodes[ AncOfNodes[i][j - 1] ][j - 1];
  78. }
  79.  
  80. int GoTopTo(int u ,int k){
  81.         int Res = u;
  82.         while( k ){
  83.             int Log = (int)log2(k);
  84.             Res = AncOfNodes[Res][Log];
  85.             k -= (1 << Log);
  86.         }
  87.         return Res;
  88. }
  89.  
  90. void Memset(int n) {
  91.     for(int i = 0 ; i <= n ; i++) idx[i] = -1;
  92. }
  93.  
  94. /// ------------------------------------------------------------------ ///
  95.  
  96. void SolveQuery() {
  97.         int u ,v;
  98.         scanf("%d%d" ,&u ,&v);
  99.  
  100.         int L = idx[u] ,R = idx[v];
  101.         if( L > R )swap(L ,R);
  102.         ii Ancestor = GetAncestor(L ,R);
  103.  
  104.         int AncHigh = DfsSpTree[ idx[Ancestor.F] ][1] ,
  105.             Uhigh   = DfsSpTree[ idx[u] ][1],
  106.             Vhigh   = DfsSpTree[ idx[v] ][1];
  107.  
  108.         int Ans = -1;
  109.         if( Uhigh == Vhigh ) {
  110.                 Ans = Ancestor.F;
  111.         } else if( Uhigh > Vhigh ) {
  112.                 int Diff = Vhigh - AncHigh;
  113.                 int DepthOfAns = (AncHigh + (Uhigh - Diff)) >> 1;
  114.                 int Kth_Anc = Uhigh - DepthOfAns;
  115.                 Ans = GoTopTo(u ,Kth_Anc);
  116.         } else if( Uhigh < Vhigh ) {
  117.                 int Diff = Uhigh - AncHigh;
  118.                 int DepthOfAns = (AncHigh + (Vhigh - Diff)) >> 1;
  119.                 int Kth_Anc = Vhigh - DepthOfAns;
  120.                 Ans = GoTopTo(v ,Kth_Anc);
  121.         }
  122.  
  123.         printf("%d\n" ,Ans);
  124. }
  125.  
  126. int main() {
  127.         scanf("%d" ,&n);
  128.         for(int i=1 ; i <= n ; i++) {
  129.                 int L ,R; scanf("%d%d" ,&L ,&R);
  130.                 Tree[i][0] = L;
  131.                 Tree[i][1] = R;
  132.                 Par[L] = Par[R] = i;
  133.         }
  134.  
  135.         Memset(n + 1);
  136.         Dfs_Pre_Order();
  137.         FillSparseTable(DfsSize ,(int)log2(DfsSize));
  138.         FillAncsOfNodes(n , (int)log2(n));
  139.  
  140.         scanf("%d" ,&Q);
  141.         while( Q-- ) SolveQuery();
  142.     return 0;
  143. }
  144.  
Add Comment
Please, Sign In to add comment