Submit Info #2997

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp cookies AC 1453 ms 88.18 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.55 MiB
line_00 AC 1371 ms 74.79 MiB
line_01 AC 1453 ms 88.18 MiB
line_02 AC 755 ms 11.64 MiB
line_03 AC 335 ms 79.51 MiB
line_04 AC 422 ms 52.04 MiB
random_00 AC 1028 ms 73.03 MiB
random_01 AC 1086 ms 86.38 MiB
random_02 AC 659 ms 10.38 MiB
random_03 AC 309 ms 79.41 MiB
random_04 AC 346 ms 51.67 MiB

#include<bits/stdc++.h> using namespace std; int main(void) { long n, q; cin >> n >> q; vector<int> par(n); for(int i=1; i<n; i++) cin >> par[i]; vector<int> h(n, -1); { auto dfs = [&](auto dfs, long cur) -> long { if(cur == 0) return h[cur] = 0; if(h[cur] != -1) return h[cur]; return h[cur] = 1 + dfs(dfs, par[cur]); }; for(int i=0; i<n; i++) dfs(dfs, i); } long d = 1; while(1L<<d < n) d++; vector<vector<long>> park(n, vector<long>(d)); { for(long i=0; i<n; i++) park[i][0] = par[i]; for(long k=1; k<d; k++) for(long i=0; i<n; i++) park[i][k] = park[park[i][k-1]][k-1]; } for(long i=0; i<q; i++) { long u, v; cin >> u >> v; if(h[u] > h[v]) swap(u, v); assert(h[u] <= h[v]); for(long i=d-1; i>=0; i--) if(h[v]-h[u] >= 1L<<i) v = park[v][i]; assert(h[v] == h[u]); if(v == u) { cout << v << endl; continue; } for(long i=d-1; i>=0; i--) if(park[v][i] != park[u][i]) v = park[v][i], u = park[u][i]; cout << park[v][0] << endl; } }