| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1183830 | aminjon__ | Treasure Hunt (CEOI11_tre) | C++17 | 0 ms | 0 KiB |
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#define all(x) (x).begin(), (x).end()
#define endl '\n'
typedef unsigned int uint;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const int maxn = 400000;
vector<vector<int>> T;
vector<int> B;
int d[maxn + 1];
int x = 1;
void Tbuild(int n)
{
B.resize(n + 1);
B[0] = -1;
for (int i = 1; i <= n; i++)
{
B[i] = B[i >> 1] + 1;
}
T.assign(1 + B[n], vector<int>(n + 1));
}
void init()
{
Tbuild(maxn + 1);
}
void path(int a, int s)
{
int ls = a;
for (int i = 1; i <= s; i++)
{
x++;
d[x] = d[ls] + 1;
T[0][x] = ls;
for (int j = 1; j <= B[x]; j++)
{
T[j][x] = T[j - 1][T[j - 1][x]];
}
ls = x;
}
}
int lift(int a, int up)
{
for (int i = B[maxn]; i >= 0; i--)
{
if ((1 << i) & up)
{
a = T[i][a];
}
}
return a;
}
int lca(int a, int b)
{
if (d[a] > d[b])
{
swap(a, b);
}
b = lift(b, d[b] - d[a]);
if (b == a)
{
return a;
}
for (int i = B[maxn]; i >= 0; i--)
{
int pA = T[i][a];
int pB = T[i][b];
if (pA != pB)
{
a = pA;
b = pB;
}
}
return T[0][a];
}
int dig(int a, int b)
{
int P = lca(a, b);
int L = d[a] - d[P] + d[b] - d[P] + 1;
int lt = d[a] - d[P] + 1;
int el = (L+1)/2;
if (el <= lt)
{
return lift(a, el - 1);
}
else
{
return lift(b, L - el);
}
}