fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FILENAME "MAIN"
  4. #define ll long long 
  5. #define el cout << '\n'
  6. #define ii pair<ll, ll>
  7. #define fi first 
  8. #define se second 
  9. #define pb push_back
  10. #define YES cout << "YES", el
  11. #define NO cout << "NO", el
  12. #define print_type cout
  13. #define print_el print_type << '\n'
  14. #define DEBUG(...) [](auto && ... x) {int i = 0; ((print_type << (i++ ? " " : "") << x), ...), print_el;} (__VA_ARGS__)
  15. #define bit(mask, i) (((mask) >> (i)) & 1)
  16. #define BIT(n) (1ll << (n))
  17.  
  18. using namespace std;
  19.  
  20. const bool is_brute = 0;
  21. const bool multi_test = 0;
  22.  
  23. const int maxn = 2e5;
  24. const int maxlog = 17;
  25.  
  26. int n, q, up[maxn + 10][maxlog + 10], tin[maxn + 10], tout[maxn + 10], timer = 0;
  27. vector<int> adj[maxn + 10];
  28.  
  29. void DFS(int top)
  30. {
  31.     tin[top] = ++timer;
  32.     for (int next_top : adj[top])
  33.     {
  34.         if (next_top == up[top][0])
  35.             continue;
  36.         up[next_top][0] = top;
  37.         DFS(next_top);
  38.     }
  39.     tout[top] = timer;
  40. }
  41. bool isAncestor(int x, int y)
  42. {
  43.     if (x == 0)
  44.         return 1;
  45.     return tin[x] <= tin[y] && tin[y] <= tout[x];
  46. }
  47. int getLCA(int x, int y)
  48. {
  49.     if (isAncestor(x, y))
  50.         return x;
  51.     if (isAncestor(y, x))
  52.         return y;
  53.     for (int i = maxlog; i >= 0; i--)
  54.         if (!isAncestor(up[x][i], y))
  55.             x = up[x][i];
  56.     return up[x][0];
  57. }
  58.  
  59. void solve()
  60. {
  61.     cin >> n >> q;
  62.     for (int i = 2; i <= n; i++)
  63.     {
  64.         int p;
  65.         cin >> p;
  66.         adj[p].push_back(i);
  67.     }
  68.     DFS(1);
  69.     for (int j = 1; j <= maxlog; j++)
  70.         for (int i = 1; i <= n; i++)
  71.             up[i][j] = up[up[i][j - 1]][j - 1];
  72.     while (q--)
  73.     {
  74.         int u, v;
  75.         cin >> u >> v;
  76.         cout << getLCA(u, v), el;
  77.     }
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  83.     if (fopen(FILENAME".INP", "r"))
  84.     {
  85.         freopen(FILENAME".INP", "r", stdin);
  86.         if (is_brute)
  87.             freopen(FILENAME"_TRAU.OUT", "w", stdout);
  88.         else
  89.             freopen(FILENAME".OUT", "w", stdout);
  90.     }
  91.  
  92.     int ntest;
  93.     if (multi_test)
  94.         cin >> ntest;
  95.     else
  96.         ntest = 1;
  97.     for (int itest = 1; itest <= ntest; itest++)
  98.     {
  99.         // cout << itest, el;
  100.         solve();
  101.     }
  102. }
Success #stdin #stdout 0.01s 10760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F4rzFF
language:
C++14 (gcc 8.3)
created:
9 hours 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!