This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 4000000 + 10;
int n, q, t;
int seq[nax];
vi V[nax];
int par[nax][19], dp[nax];
void dfs(int x) {
for(int nbh : V[x]) {
dp[nbh] = dp[x] + 1;
dfs(nbh);
par[nbh][0] = x;
}
}
int lca(int a, int b) {
if(dp[a] < dp[b]) swap(a, b);
for(int i = 18; i >= 0; --i) {
if(dp[par[a][i]] >= dp[b]) {
a = par[a][i];
}
}
if(a == b) return a;
for(int i = 18; i >= 0; --i) {
if(par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> t;
int start = 1;
for(int i = 1; i <= n; ++i) {
cin >> seq[i];
for(int j = start; j < start + i; ++j) {
if(j <= seq[i]) V[j].PB(j + i);
if(j >= seq[i]) V[j].PB(j + i + 1);
}
start += i;
}
start += n + 1;
dp[1] = 1;
dfs(1);
for(int s = 1; s <= 18; ++s) {
for(int i = 1; i <= start; ++i) {
par[i][s] = par[par[i][s - 1]][s - 1];
}
}
while(q--) {
ll x, y;
cin >> x >> y;
cout << lca(x, y) << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |