Submit Info #3001

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp cookies RE 229 ms 78.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
line_00 RE 206 ms 66.25 MiB
line_01 RE 229 ms 78.51 MiB
line_02 RE 108 ms 8.38 MiB
line_03 RE 217 ms 72.84 MiB
line_04 RE 174 ms 47.30 MiB
random_00 RE 204 ms 66.27 MiB
random_01 RE 227 ms 78.55 MiB
random_02 RE 107 ms 8.38 MiB
random_03 RE 217 ms 72.88 MiB
random_04 RE 171 ms 47.30 MiB

#include<bits/stdc++.h> using namespace std; struct LCA { vector<vector<long>> park; vector<long> h; long n, d; LCA(vector<long> &par) { // par[root] == -1 n = par.size(); h.assign(n, -1); { auto dfs = [&](auto dfs, long cur) -> long { if(par[cur] == -1) return h[cur] = 0; if(h[cur] != -1) return h[cur]; return h[cur] = 1 + dfs(dfs, par[cur]); }; for(long i=0; i<n; i++) dfs(dfs, i); } for(d=0; 1L<<d < n; d++); park.assign(d, vector<long>(n)); copy(par.begin(), par.end(), park[0].begin()); for(long k=1; k<d; k++) for(long i=0; i<n; i++) park[k][i] = park[k-1][park[k-1][i]]; } long query(long u, long v) const { if(h[u] > h[v]) swap(u, v); for(long i=d-1; i>=0; i--) if(h[v]-h[u] >= 1L<<i) v = park[i][v]; if(v == u) return v; for(long i=d-1; i>=0; i--) if(park[i][v] != park[i][u]) v = park[i][u], u = park[i][u]; return park[0][v]; } }; int main(void) { long n, q; cin >> n >> q; vector<long> par(n); par[0] = -1; for(int i=1; i<n; i++) cin >> par[i]; LCA lca(par); for(long i=0; i<q; i++) { long u, v; cin >> u >> v; cout << lca.query(u, v) << endl; } }