#include "treasure.h"
#define N 400000
#define LN 18 /* LN = floor(log2(N)) */
int min(int a, int b) { return a < b ? a : b; }
int ii_[N + 1], dd[N + 1], dd_[N + 1], pp[N + 1][LN + 1], pp_[N + 1][LN + 1], n, n_;
void init() {
ii_[n] = n_++ + 1, dd[n] = 0, n++;
}
int search(int i_) {
int lower = 0, upper = n;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (ii_[i] <= i_)
lower = i;
else
upper = i;
}
return lower;
}
void path(int p_, int sz) {
int p, l, d;
ii_[n] = n_ + 1, n_ += sz;
p = search(p_);
dd[n] = d = dd[p] + 1, pp[n][0] = p, pp_[n][0] = p_;
for (l = 1; 1 << l <= d; l++)
pp[n][l] = pp[pp[n][l - 1]][l - 1], pp_[n][l] = pp_[pp[n][l - 1]][l - 1];
dd_[n] = dd_[p] + p_ - ii_[p] + 1;
n++;
}
void get(int i_, int j_, int *d1, int *d2) {
int i = search(i_), j = search(j_), l;
if (dd[i] < dd[j]) {
int tmp, *tmp_;
tmp = i, i = j, j = tmp, tmp = i_, i_ = j_, j_ = tmp, tmp_ = d1, d1 = d2, d2 = tmp_;
}
*d1 = (dd_[i] + i_ - ii_[i]), *d2 = (dd_[j] + j_ - ii_[j]);
for (l = LN; l >= 0; l--)
if (dd[i] - dd[j] >= 1 << l)
i_ = pp_[i][l], i = pp[i][l];
if (i != j) {
for (l = LN; l >= 0; l--)
if (dd[i] >= 1 << l && pp[i][l] != pp[j][l])
i_ = pp_[i][l], i = pp[i][l], j_ = pp_[j][l], j = pp[j][l];
i_ = pp_[i][0], i = pp[i][0], j_ = pp_[j][0], j = pp[j][0];
}
i_ = min(i_, j_);
*d1 -= dd_[i] + i_ - ii_[i], *d2 -= dd_[i] + i_ - ii_[i];
}
int ancestor(int i_, int d) {
int i = search(i_), d_, l;
d_ = (dd_[i] + i_ - ii_[i]) - d;
if (dd_[i] > d_) {
for (l = LN; l >= 0; l--)
if (dd[i] >= 1 << l && dd_[pp[i][l]] > d_)
i_ = pp_[i][l], i = pp[i][l];
i_ = pp_[i][0], i = pp[i][0];
}
return ii_[i] + d_ - dd_[i];
}
int dig(int i_, int j_) {
int d1, d2;
get(i_, j_, &d1, &d2);
return d1 >= (d1 + d2) / 2 ? ancestor(i_, (d1 + d2) / 2) : ancestor(j_, d1 + d2 - (d1 + d2) / 2);
}
Compilation message
tre.c:1:10: fatal error: treasure.h: No such file or directory
1 | #include "treasure.h"
| ^~~~~~~~~~~~
compilation terminated.
tregrader.c:9:10: fatal error: cassert: No such file or directory
9 | #include <cassert>
| ^~~~~~~~~
compilation terminated.
