Cod sursa(job #2677957)

Utilizator retrogradLucian Bicsi retrograd Data 27 noiembrie 2020 20:47:01
Problema Stramosi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#ifdef LOCAL
#include <debug.hpp>
#else
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,tune=native")
#define debug(...)
#endif 

#include <bits/stdc++.h>

using namespace std;

struct Lift {
  struct Data { int par, link, dep; };
  vector<Data> T;

  int Add(int par) {
    int ret = T.size();
    if (par == -1) T.push_back(Data{-1, ret, 0});
    else {
      int link = par, a1 = T[par].link, a2 = T[a1].link;
      if (2 * T[a1].dep == T[a2].dep + T[par].dep)
        link = a2;
      T.push_back(Data{par, link, T[par].dep + 1});
    }
    return ret;
  }
  int Kth(int node, int k) {
    int seek = T[node].dep - k;
    if (seek < 0) return -1;
    while (T[node].dep > seek) 
      node = (T[T[node].link].dep >= seek) 
        ? T[node].link : T[node].par;
    return node;
  }
  int LCA(int a, int b) {
    if (T[a].dep < T[b].dep) swap(a, b);
    while (T[a].dep > T[b].dep) 
      a = (T[T[a].link].dep >= T[b].dep) 
        ? T[a].link : T[a].par;
    while (a != b) {
      if (T[a].dep == 0) return -1;
      if (T[a].link != T[b].link) 
        a = T[a].link, b = T[b].link;
      else a = T[a].par, b = T[b].par;
    }
    return a;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  ifstream cin("stramosi.in");
  ofstream cout("stramosi.out");

  int n, m; cin >> n >> m;
  Lift L;
  for (int i = 0; i < n; ++i) {
    int par; cin >> par; --par;
    L.Add(par);
  }
  for (int i = 0; i < m; ++i) {
    int a, k; cin >> a >> k; --a;
    cout << 1 + L.Kth(a, k) << '\n';
  }
  return 0;
}