fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> ii;
  5. typedef vector<ii> vii;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. #define FOR(i,n) for (i = 0; i < n; ++i)
  9. #define FORK(i,k,n) for (i = k; i <= n; ++i)
  10. #define FORR(i,k,n) for (i = k; i >= n; --i)
  11.  
  12. #define re(a,b)   memset(a,b,sizeof(a))
  13. #define sz(a)      (int)(a.size())
  14. #define MIN(a,b)     (a) = min((a),(b))
  15. #define MAX(a,b)     (a) = max((a),(b))
  16. #define input(in)    freopen(in,"r",stdin)
  17. #define output(out)  freopen(out,"w",stdout)
  18. #define ALL(a)       a.begin(),a.end()
  19. #define RALL(a)      a.rbegin(),a.rend()
  20. #define LEN(a)       (int)(a.length())
  21.  
  22. #define FIN(x)       freopen(x,"r",stdin)
  23. #define FOUT(x)      freopen(x,"w",stdout)
  24. #define FCLOSE       {fclose(stdin); fclose(stdout);}
  25.  
  26. #define fi           first
  27. #define se           second
  28. #define pb           push_back
  29. #define mp           make_pair
  30. #define  M           1010
  31. #define INF          1001001001
  32.  
  33. vi a[M]; //
  34. vi b;
  35. ii c[M];  // euler tour vector whose first element stores the height of node and stores the node encountered in euler tour of graph
  36. ii tree[4*M]; // an array of pairs , whose first element stores the height and second stores the node encountered in the euler tour  
  37. int f[M];    // array to store first occurrence
  38. int h[M];    // height of each node
  39. bool v[M];
  40. /*** building segment tree ***/
  41. void st(int i,int s,int e)
  42. {
  43.     if(s>e)
  44.     return ;
  45.     if(s==e)
  46.     {
  47.     tree[i].fi=c[s].fi;
  48.     tree[i].se=c[s].se;
  49.      return;
  50.     }
  51.     int k= (s+e)/2;
  52.     st(2*i,s,k);
  53.     st(2*i+1,k+1,e);
  54.     if(tree[2*i].fi<=tree[2*i+1].fi) // if min height of the left tree is less than the min height of right 
  55.     {
  56.         tree[i].fi=tree[2*i].fi;  // storing the height
  57.         tree[i].se=tree[2*i].se;  // storing the node
  58.     }
  59.     else
  60.     {
  61.         tree[i].fi=tree[2*i+1].fi;
  62.         tree[i].se=tree[2*i+1].se;
  63.     }
  64. }
  65. /**** finding the minimum int the range *****/
  66. ii min(int i,int s,int e,int n,int m) // n lower and m upper index of given range
  67. {
  68.     if(e<n || s>m || s>e)
  69.      {
  70.          ii j ;
  71.          j.fi=INF; // making a pair to return the pair if the  the range is not in required range
  72.          j.se=INF;
  73.          return j;
  74.      }
  75.     else if(s>=n && e<=m )
  76.      {
  77.          return tree[i];
  78.      }
  79.     int k=(s+e)/2;
  80.     ii t1=min(2*i,s,k,n,m);
  81.     ii t2=min(2*i+1,k+1,e,n,m);
  82.     if(t1.fi<=t2.fi)
  83.     {
  84.         return  t1;
  85.     }
  86.     else
  87.     {
  88.  
  89.         return t2;
  90.     }
  91. }
  92. /**** dfs which does euler tour of the graph also stores the height and its first occurrence int the euler tour ****/
  93. void dfs(int n,int height)
  94. {
  95.     b.pb(n);  // vector keeping track of the euler tour
  96.     int i;
  97.     h[n]=height; // to store the height of each node 
  98.     f[n]=sz(b)-1; //  to store the first occurrence of each node 
  99.      v[n]=true;  
  100.     FOR(i,sz(a[n]))
  101.     {
  102.       if(v[a[n][i]]==false)
  103.       {
  104.        dfs(a[n][i],height+1);
  105.       b.pb(n); // adding the parent again after 
  106.       }
  107.     }
  108. }
  109. /*** initializing everything *****/
  110. void init() //  to initialize all the arrays 
  111. {
  112.     int i;
  113.     b.clear();
  114.     FOR(i,M)
  115.     {
  116.         a[i].clear();
  117.         f[i]=0;
  118.         h[i]=0;
  119.         v[i]=false;
  120.     }
  121.     FOR(i,4*M)
  122.     {
  123.       tree[i].fi=INF;
  124.       tree[i].se=0;
  125.     }
  126. }
  127. // ii  is typedef which represents pair<int,int>  
  128. int main()
  129. {
  130.     ios_base::sync_with_stdio(false);cin.tie(0);
  131.     int t;
  132.     cin >> t;
  133.     int mv=1;
  134.     while(t--)
  135.     {
  136.         init();
  137.         int n,i,j,m,x,y;
  138.         cin >> n;
  139.         FORK(i,1,n)
  140.         {
  141.             cin >> m;
  142.             FOR(j,m)
  143.             {
  144.                 cin >> x;
  145.                 a[i].pb(x);
  146.             }
  147.         }
  148.         b.pb(0); // storing first elemnent 0
  149.         dfs(1,1); // taking one as root node
  150.         FOR(i,sz(b)) // creating the pair array to make segment tree 
  151.         {
  152.          //   cout << b[i] << "\n";
  153.          c[i].fi=h[b[i]]; // storing the height of the node
  154.          c[i].se=b[i];  //storing the node
  155.         }
  156.         n=sz(b); // taking the size of euler tour
  157.         st(1,1,n); // making segment tree
  158.         //cout << "\n";*/
  159.         /*** query part ***/
  160.         int q;
  161.         cin >> q;
  162.         cout << "Case " << mv << ":\n";
  163.         while(q--)
  164.         {
  165.             int c;
  166.             cin >> x >> y;
  167.             if(f[y]<f[x])
  168.             {
  169.               swap(x,y);
  170.             }
  171.            ii  k=min(1,1,n,f[x],f[y]); //  the minimum height pair
  172.             cout << k.se  << "\n"; // the minimum height node
  173.         }
  174.         mv++;
  175.     }
  176.     return 0;
  177. }
  178.  
Success #stdin #stdout 0s 16136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1:
Case 2:
https://ideone.com/uQcFV4
language:
C++ (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!