Advertisement
ismaeil

Algo Project 1

Jul 23rd, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5e1;
  5. const int OO = INT_MAX;
  6. int Tree[N][2] ,Par[N];
  7. vector< int > Dist;
  8. int n ,Q;
  9.  
  10. vector< int > GetLcaPath(int u ,int v){
  11.     vector< int > PathV;
  12.     vector< int > PathU;
  13.  
  14.         while( u != v ){
  15.                 if( Dist[u] < Dist[v] ){
  16.                         PathV.push_back(v);
  17.                         v = Par[v];
  18.                 } else if( Dist[u] > Dist[v] ){
  19.                         PathU.push_back(u);
  20.                         u = Par[u];
  21.                 } else {
  22.                         PathV.push_back(v);
  23.                         PathU.push_back(u);
  24.                         u = Par[u];
  25.                         v = Par[v];
  26.                 }
  27.         } PathV.push_back( v );
  28.  
  29.         for(int i = PathU.size() - 1 ; i >= 0 ; i --) PathV.push_back( PathU[i] );
  30.     return PathV;
  31. }
  32.  
  33. void BFS() {
  34.         Dist.assign(n + 1 ,OO);
  35.         queue< int > Q;
  36.         Dist[1] = 0;
  37.         Q.push(1);
  38.  
  39.         while( !Q.empty() ) {
  40.                 int front = Q.front(); Q.pop();
  41.  
  42.                 for(int i=0 ; i < 2 ; i++){
  43.                         if( Tree[front][i] != -1 && Dist[Tree[front][i]] == OO ){
  44.                                 Dist[ Tree[front][i] ] = Dist[front] + 1;
  45.                                 Q.push( Tree[front][i] );
  46.                         }
  47.                 }
  48.         }
  49. }
  50.  
  51. void Solve(){
  52.         int u ,v ,Ans;
  53.         scanf("%d%d" ,&u ,&v);
  54.  
  55.         vector< int > Path = GetLcaPath(u ,v);
  56.         Ans = Path[ (int)Path.size() / 2 ];
  57.         printf("%d\n" ,Ans);
  58. }
  59.  
  60. int main() {
  61.         scanf("%d" ,&n);
  62.         for(int i=1 ; i <= n ; i++) {
  63.                 int L ,R; scanf("%d%d" ,&L ,&R);
  64.                 Tree[i][0] = L;
  65.                 Tree[i][1] = R;
  66.                 Par[L] = Par[R] = i;
  67.         }
  68.  
  69.         BFS();
  70.  
  71.         scanf("%d" ,&Q);
  72.         while( Q-- ) Solve();
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement