#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f first
#define s second
const int MAXN = 1e6 + 5;
int n = 1;
int last = 1;
bool pe[MAXN];
int p[MAXN];
int up[MAXN][21];
int pval[MAXN];
pair<int, int> e[MAXN];
map<pair<int, int>, int> seg;
int h[MAXN];
int realh[MAXN];
void build_up(int v) {
up[v][0] = p[v];
for (int i = 1; i < 21; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
}
int get_node(int a) {
return prev(seg.upper_bound({a, 2e9}))->s;
}
int get_realh(int a) {
int v = get_node(a);
// cout << "gr " << a << " = " << realh[v] - (e[v].s - a) << endl;
return realh[v] - (e[v].s - a);
}
void init() {
// val[0] = 0;
p[0] = 0;
build_up(0);
e[0] = {0, 0};
seg[e[0]] = 0;
h[0] = 0;
realh[0] = 1;
}
void dbg() {
rep(i, n) {
cout << "node " << i << endl;
cout << "p " << p[i] << endl;
cout << "pval " << pval[i] << endl;
cout << "h " << h[i] << endl;
cout << "realh " << realh[i] << endl;
cout << "seg " << e[i].f << ' ' << e[i].s << endl;
cout << endl;
}
}
void path(int a, int s) {
a--;
int v = get_node(a);
// cout << " : " << v << endl;
if (a == e[v].s) {
// cout << "exp" << endl;
// explicit parent, no need to create extra node
pe[n] = true;
p[n] = v;
build_up(n);
pval[n] = a;
e[n] = {last, last + s - 1};
seg[e[n]] = n;
h[n] = h[v] + 1;
realh[n] = realh[v] + s;
last += s;
n++;
} else {
// cout << "imp" << endl;
// create extra node
pe[n] = false;
p[n] = p[v];
build_up(n);
pval[n] = a;
e[n] = {last, last};
seg[e[n]] = n;
h[n] = h[v];
realh[n] = get_realh(a) + 1;
last++;
n++;
a = last; // in call to path() will be decreased
s--;
if (s > 0) {
path(a, s);
return;
}
}
// dbg();
}
int fgetup(int a, int x, int v, int h) {
int tarh = h - x;
for (int i = 20; i >= 0; --i) {
if (realh[up[v][i]] >= tarh) {
v = up[v][i];
// cout << " -- " << i << ' ' << v << endl;
}
}
if (pe[v] || tarh == realh[v]) {
return e[v].s - (realh[v] - tarh);
} else {
return pval[v] - (realh[v] - tarh - 1);
}
}
int getup(int a, int x) {
// cout << "getup " << a << ' ' << x << endl;
int v = get_node(a);
int h = get_realh(a);
// cout << get_realh(a) << endl;
// cout << v << ' ' << tarh << endl;
return fgetup(a, x, v, h);
// cout << " : " << v << endl;
}
void align(int &a, int &b) {
int ah = get_realh(a), bh = get_realh(b);
if (ah > bh) {
a = getup(a, ah - bh);
} else {
b = getup(b, bh - ah);
}
}
void align_vertex(int &v1, int &v2) {
for (int i = 20; i >= 0; --i) {
if (h[up[v1][i]] >= h[v2]) {
v1 = up[v1][i];
}
}
}
int find_lca(int a, int b) {
// cout << "find_lca " << a << ' ' << b << endl;
align(a, b);
if (a == b) return a;
// cout << "aligned " << a << ' ' << b << endl;
// now they are definitely on different explicit edges and neither of them is parent of another
int v1 = get_node(a), v2 = get_node(b);
// cout << v1 << ' ' << v2 << endl;
align_vertex(v1, v2);
align_vertex(v2, v1);
// cout << v1 << ' ' << v2 << endl;
for (int i = 20; i >= 0; --i) {
if (up[v1][i] != up[v2][i]) {
v1 = up[v1][i];
v2 = up[v2][i];
}
}
// cout << v1 << ' ' << v2 << endl;
if (pe[v1] && pe[v2]) {
assert(p[v1] == p[v2]);
return e[p[v1]].s;
}
// a = e[v1].s, b = e[v2].s;
assert(p[v1] == p[v2]);
if (pe[v1]) {
a = e[v1].s;
} else {
a = pval[v1];
}
if (pe[v2]) {
b = e[v2].s;
} else {
b = pval[v2];
}
// // cout << a << ' ' << b << endl;
// return min(a, b);
int ac = a, bc = b;
int h1 = get_realh(ac), h2 = get_realh(bc);
if (h1 > h2) {
ac = getup(ac, h1 - h2);
} else {
bc = getup(bc, h2 - h1);
}
// cout << ac << ' ' << bc << endl;
int av = get_node(ac), ah = get_realh(ac), bv = get_node(bc), bh = get_realh(bc);
int l = -1, r = 1e9 + 8;
while (r - l > 1) {
int m = l + (r - l) / 2;
if (fgetup(ac, m, av, ah) == fgetup(bc, m, bv, bh)) {
r = m;
} else {
l = m;
}
}
return getup(ac, r);
}
int dig(int a, int b) {
a--; b--;
// dbg();
// int ac = a, bc = b;
// int h1 = get_realh(ac), h2 = get_realh(bc);
// if (h1 > h2) {
// ac = getup(ac, h1 - h2);
// } else {
// bc = getup(bc, h2 - h1);
// }
// // cout << ac << ' ' << bc << endl;
// int av = get_node(ac), ah = get_realh(ac), bv = get_node(bc), bh = get_realh(bc);
// int l = -1, r = 1e9 + 8;
// while (r - l > 1) {
// int m = l + (r - l) / 2;
// if (fgetup(ac, m, av, ah) == fgetup(bc, m, bv, bh)) {
// r = m;
// } else {
// l = m;
// }
// }
int lca = find_lca(a, b);
int lch = get_realh(lca);
int uh = get_realh(a), vh = get_realh(b);
int d = uh + vh - 2 * lch;
int da = d / 2;
if (uh >= vh) {
return getup(a, da) + 1;
} else {
return getup(b, d - da) + 1;
}
// int u0 = get_node(a), v0 = get_node(b);
// int u = u0, v = v0;
// for (int i = 20; i >= 0; --i) {
// if (h[up[u][i]] <= h[v]) {
// u = up[u][i];
// }
// }
// for (int i = 20; i >= 0; --i) {
// if (h[up[v][i]] <= h[u]) {
// v = up[v][i];
// }
// }
// if (u == v) {
// // one of nodes is parent of other
// int uh = get_realh(u), vh = get_realh(v);
// if (uh > )
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
504 KB |
Output is correct |
| 2 |
Correct |
17 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1860 ms |
57688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1173 ms |
9240 KB |
Output is correct |
| 2 |
Correct |
1677 ms |
36332 KB |
Output is correct |
| 3 |
Correct |
1534 ms |
36376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1399 ms |
36328 KB |
Output is correct |
| 2 |
Correct |
3845 ms |
7672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1506 ms |
36228 KB |
Output is correct |
| 2 |
Correct |
3961 ms |
70192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2064 ms |
18924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2541 ms |
63440 KB |
Output is correct |
| 2 |
Correct |
556 ms |
68092 KB |
Output is correct |
| 3 |
Correct |
518 ms |
68156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3522 ms |
66824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3579 ms |
66776 KB |
Output is correct |
