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 in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = (1000 + 1) * (1000 + 2) + 50;
vector <int> g[N];
int up[N][25];
int n, q, t;
int to[N], mk[N];
vector <int> lv[1050];
int nm[N];
int tin[N], tout[N], tim;
void dfs(int v, int pr) {
tin[v] = tim++;
up[v][0] = pr;
for (auto u : g[v]) {
if (u == pr) {
continue;
}
dfs(u, v);
}
tout[v] = tim++;
}
int isa(int x, int y) {return (tin[x] <= tin[y] && tout[x] >= tout[y]);}
int lca(int x, int y) {
if (isa(x, y)) {
return x;
}
if (isa(y, x)) {
return y;
}
for (int st = 21; st >= 0; st--) {
if (!isa(up[y][st], x)) {
y = up[y][st];
}
}
return up[y][0];
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n >> q >> t;
assert(n <= 1000);
for (int i = 1; i <= n + 1; i++) {
for (int j = i * (i - 1) / 2 + 1; j <= i * (i + 1) / 2; j++) {
nm[j] = sz(lv[i]);
lv[i].pb(j);
}
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
mk[x] = 1;
g[x].pb(lv[i + 1][nm[x]]);
g[x].pb(lv[i + 1][nm[x] + 1]);
to[lv[i + 1][nm[x]]] = 1;
to[lv[i + 1][nm[x] + 1]] = 1;
}
for (int i = 1; i <= n; i++) {
int k = 0;
for (int j = i * (i - 1) / 2 + 1; j <= i * (i + 1) / 2; j++) {
if (mk[j]) {
continue;
}
while (to[lv[i + 1][k]]) {
k++;
}
g[j].pb(lv[i + 1][k]);
k++;
}
}
tin[0] = tim++;
tout[0] = 1e9;
dfs(1, 0);
for (int st = 1; st <= 21; st++) {
for (int i = 1; i <= (n + 1) * (n + 2); i++) {
up[i][st] = up[up[i][st - 1]][st - 1];
}
}
while (q--) {
int x, y;
cin >> x >> y;
cout << lca(x, y) << el;
}
}
# | 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... |