Submission #1183842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183842		aminjon__	Treasure Hunt (CEOI11_tre)	C++17	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>
#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);
    }
}
int main()
{
  int num_calls;
  cin >> num_calls;
  for (int i = 1; i <= num_calls; i++)
  {
    char call[2];
    int a, b;
    cin >> call[0] >> a >> b;
    if (call[0] == 'i')
      init();
    else if (call[0] == 'p')
      path(a, b);
    else
        cout<<dig(a,b)<<endl;
  }
  return 0;
}

• Subtask 1: 0 / 100