mihaimarcel21

binary_tree

Jan 24th, 2021
553
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int lca(int u, int v)
  6. {
  7.     int ans = 0;
  8.     while(v != u) {
  9.         if(v < u)
  10.             swap(u, v);
  11.         v >>= 1;
  12.         ++ans;
  13.     }
  14.     return ans;
  15. }
  16.  
  17. void test_case()
  18. {
  19.     int Q;
  20.     cin >> Q;
  21.     while(Q--) {
  22.         int u, v;
  23.         cin >> u >> v;
  24.         cout << lca(u, v) << '\n';
  25.     }
  26. }
  27.  
  28. int main()
  29. {
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     cout.tie(nullptr);
  33.     int T = 1;
  34.     while(T--)
  35.         test_case();
  36. }
RAW Paste Data