CompProg

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Zeldacrafter/CompProg

:heavy_check_mark: tests/yosupo/sparse_table.lca.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include "../../code/graphs/LCA.cc"

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q; cin >> n >> q;

    vvi adj(n);
    FOR (i, 1, n) {
        int u; cin >> u;
        adj[i].pb(u);
        adj[u].pb(i);
    }

    LCA lca(adj);
    while(q--) {
        int u, v; cin >> u >> v;
        cout << lca.query(u, v) << endl;
    }
}
#line 1 "tests/yosupo/sparse_table.lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/SPT.cc"
template <typename T, typename F>
struct SPT {
  vector<vector<T>> d;
  F f;
  SPT (int n, F _f) : d(32 - __builtin_clz(n), vector<T>(n)), f{_f} {}
  SPT (const vector<T>& v, F _f) : SPT(SZ(v), _f) {
    d[0] = v;
    build();
  }
  void build() {
    for (int j = 1; (1 << j) <= SZ(d[0]); ++j) {
      for (int i = 0; i + (1 << j) <= SZ(d[0]); ++i) {
        d[j][i] = f(d[j - 1][i], d[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T query(int l, int r) { // [l, r)
    int k = 31 - __builtin_clz(r - l);
    return f(d[k][l], d[k][r - (1 << k)]);
  }
};

#line 2 "code/graphs/LCA.cc"
struct LCA {
  vi height, first;
  SPT<int, function<int(int, int)>> spt;
  LCA(vvi& adj, int root = 0) : height(SZ(adj), -1), first(SZ(adj), -1),
      spt(2 * SZ(adj) - 1, [self = this](int a, int b) {
        return self->height[a] < self->height[b] ? a : b;
      }) {
    int idx = 0;
    dfs(adj, root, idx);
    spt.build();
  }
  void dfs(vvi& adj, int v, int& idx, int h = 0) {
    first[v] = idx;
    spt.d[0][idx++] = v;
    height[v] = h;
    for (int u : adj[v]) if (first[u] == -1) {
      dfs(adj, u, idx, h + 1);
      spt.d[0][idx++] = v;
    }
  }
  int query(int a, int b) {
    ii m = minmax(first[a], first[b]);
    return spt.query(m.fi, m.se);
  }
};
#line 4 "tests/yosupo/sparse_table.lca.test.cpp"

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q; cin >> n >> q;

    vvi adj(n);
    FOR (i, 1, n) {
        int u; cin >> u;
        adj[i].pb(u);
        adj[u].pb(i);
    }

    LCA lca(adj);
    while(q--) {
        int u, v; cin >> u >> v;
        cout << lca.query(u, v) << endl;
    }
}
Back to top page