test/yosupo/lca.LCT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• Link-Cut-Tree (src/DataStructure/LinkCutTree.hpp)
• detection idiom (src/Internal/detection_idiom.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include "src/DataStructure/LinkCutTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 LinkCutTree lct(N);
 for (int i= 1; i < N; i++) {
  int p;
  cin >> p;
  lct.link(i, p);
 }
 lct.evert(0);
 while (Q--) {
  int u, v;
  cin >> u >> v;
  cout << lct.lca(u, v) << '\n';
 }
 return 0;
}

#line 1 "test/yosupo/lca.LCT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/lca
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/DataStructure/LinkCutTree.hpp"
#include <algorithm>
#include <vector>
#include <string>
#include <cstddef>
#include <utility>
#include <cassert>
#line 2 "src/Internal/detection_idiom.hpp"
#include <type_traits>
#define _DETECT_BOOL(name, ...) \
 template <class, class= void> struct name: std::false_type {}; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>>: std::true_type {}; \
 template <class T> static constexpr bool name##_v= name<T>::value
#define _DETECT_TYPE(name, type1, type2, ...) \
 template <class T, class= void> struct name { \
  using type= type2; \
 }; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>> { \
  using type= type1; \
 }
#line 9 "src/DataStructure/LinkCutTree.hpp"
template <class M= void> class LinkCutTree {
 _DETECT_BOOL(semigroup, typename T::T, decltype(&T::op));
 _DETECT_BOOL(dual, typename T::T, typename T::E, decltype(&T::mp), decltype(&T::cp));
 _DETECT_BOOL(commute, typename T::commute);
 _DETECT_TYPE(myself_or_T, typename T::T, T, typename T::T);
 _DETECT_TYPE(nullptr_or_E, typename T::E, std::nullptr_t, typename T::E);
 using T= std::conditional_t<std::is_void_v<M>, std::nullptr_t, typename myself_or_T<M>::type>;
 using E= typename nullptr_or_E<M>::type;
 struct NodeB {
  int ch[2]= {-1, -1}, par= -1;
  bool revf= 0;
 };
 template <class D, class A> struct NodeV: NodeB {
  T val;
 };
 template <class D> struct NodeV<D, void>: NodeB {};
 template <class D, bool du> struct NodeD: NodeV<D, M> {};
 template <class D> struct NodeD<D, 1>: NodeV<D, M> {
  E laz;
  bool lazf= 0;
 };
 template <class D, bool sg, bool com> struct NodeS: NodeD<D, dual_v<M>> {};
 template <class D> struct NodeS<D, 1, 1>: NodeD<D, dual_v<M>> {
  T sum;
 };
 template <class D> struct NodeS<D, 1, 0>: NodeD<D, dual_v<M>> {
  T sum, rsum;
 };
 using Node= NodeS<void, semigroup_v<M>, commute_v<M>>;
 std::vector<Node> n;
 inline void update(int i) {
  n[i].sum= n[i].val;
  if constexpr (!commute_v<M>) n[i].rsum= n[i].val;
  if (int l= n[i].ch[0]; l != -1) {
   n[i].sum= M::op(n[l].sum, n[i].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[i].rsum, n[l].rsum);
  }
  if (int r= n[i].ch[1]; r != -1) {
   n[i].sum= M::op(n[i].sum, n[r].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[r].rsum, n[i].rsum);
  }
 }
 inline void propagate(int i, const E &x) {
  if (i == -1) return;
  if (n[i].lazf) M::cp(n[i].laz, x);
  else n[i].laz= x;
  if constexpr (semigroup_v<M>) {
   M::mp(n[i].sum, x);
   if constexpr (!commute_v<M>) M::mp(n[i].rsum, x);
  }
  M::mp(n[i].val, x), n[i].lazf= 1;
 }
 inline void toggle(int i) {
  if (i == -1) return;
  std::swap(n[i].ch[0], n[i].ch[1]);
  if constexpr (semigroup_v<M> && !commute_v<M>) std::swap(n[i].sum, n[i].rsum);
  n[i].revf^= 1;
 }
 inline void push(int i) {
  if (n[i].revf) toggle(n[i].ch[0]), toggle(n[i].ch[1]), n[i].revf= 0;
  if constexpr (dual_v<M>)
   if (n[i].lazf) propagate(n[i].ch[0], n[i].laz), propagate(n[i].ch[1], n[i].laz), n[i].lazf= 0;
 }
 inline int dir(int i) {
  if (int p= n[i].par; p != -1) {
   if (n[p].ch[0] == i) return 0;
   if (n[p].ch[1] == i) return 1;
  }
  return 2;
 }
 inline void rot(int i) {
  int p= n[i].par, d= n[p].ch[1] == i;
  if (int c= n[p].ch[d]= std::exchange(n[i].ch[!d], p); c != -1) n[c].par= p;
  if (d= dir(p); d < 2) n[n[p].par].ch[d]= i;
  n[i].par= std::exchange(n[p].par, i);
  if constexpr (semigroup_v<M>) update(p);
 }
 inline void splay(int i) {
  push(i);
  for (int d; d= dir(i), d < 2; rot(i))
   if (int p= n[i].par, c= dir(p), pp= n[p].par; c < 2) push(pp), push(p), push(i), rot(d == c ? p : i);
   else push(p), push(i);
  if constexpr (semigroup_v<M>) update(i);
 }
 inline int expose(int i) {
  int r= -1;
  for (int p= i; p != -1; r= p, p= n[p].par) {
   splay(p), n[p].ch[1]= r;
   if constexpr (semigroup_v<M>) update(p);
  }
  return splay(i), r;
 }
public:
 LinkCutTree(size_t sz): n(sz) {}
 LinkCutTree(size_t sz, T val): n(sz) {
  for (int i= sz; i--;) n[i].val= val;
 }
 void evert(int k) { expose(k), toggle(k), push(k); }
 void link(int c, int p) {
  evert(c), expose(p), assert(n[c].par == -1), n[p].ch[1]= c, n[c].par= p;
  if constexpr (semigroup_v<M>) update(p);
 }
 void cut(int c, int p) {
  evert(p), expose(c), assert(n[c].ch[0] == p), n[c].ch[0]= n[p].par= -1;
  if constexpr (semigroup_v<M>) update(c);
 }
 int root(int x) {
  for (expose(x);; x= n[x].ch[0])
   if (push(x), n[x].ch[0] == -1) return splay(x), x;
 }
 int parent(int x) {
  if (expose(x), x= n[x].ch[0]; x == -1) return -1;
  for (;; x= n[x].ch[1])
   if (push(x), n[x].ch[1] == -1) return splay(x), x;
 }
 int lca(int x, int y) { return x == y ? x : (expose(x), y= expose(y), n[x].par == -1) ? -1 : y; }
 const T &get(int k) {
  static_assert(!std::is_void_v<M>, "\"get\" is not available\n");
  return expose(k), n[k].val;
 }
 T &at(int k) {
  static_assert(!std::is_void_v<M> && !semigroup_v<M>, "\"at\" is not available\n");
  return expose(k), n[k].val;
 }
 template <class L= M> const std::enable_if_t<semigroup_v<L>, T> &operator[](size_t k) { return get(k); }
 template <class L= M> std::enable_if_t<!semigroup_v<L>, T> &operator[](size_t k) { return at(k); }
 void set(int k, const T &v) {
  static_assert(!std::is_void_v<M>, "\"set\" is not available\n");
  expose(k), n[k].val= v;
  if constexpr (semigroup_v<M>) update(k);
 }
 void mul(int k, const T &v) {
  static_assert(semigroup_v<M> && commute_v<M>, "\"mul\" is not available\n");
  expose(k), n[k].val= M::op(n[k].val, v), update(k);
 }
 // [a,b] closed section
 T prod(int a, int b) {
  static_assert(semigroup_v<M>, "\"prod\" is not available\n");
  return a == b ? get(a) : (evert(a), expose(b), assert(n[a].par != -1), n[b].sum);
 }
 // [a,b] closed section
 void apply(int a, int b, const E &v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  evert(a), expose(b), assert(a == b || n[a].par != -1), propagate(b, v), push(b);
 }
 static std::string which_unavailable() {
  std::string ret= "";
  if constexpr (semigroup_v<M>) ret+= "\"at\" ";
  else ret+= "\"prod\" ";
  if constexpr (!semigroup_v<M> || !commute_v<M>) ret+= "\"mul\" ";
  if constexpr (!dual_v<M>) ret+= "\"apply\" ";
  if constexpr (std::is_void_v<M>) ret+= "\"get\" \"set\" ";
  return ret;
 }
};
#line 6 "test/yosupo/lca.LCT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 LinkCutTree lct(N);
 for (int i= 1; i < N; i++) {
  int p;
  cin >> p;
  lct.link(i, p);
 }
 lct.evert(0);
 while (Q--) {
  int u, v;
  cin >> u >> v;
  cout << lct.lca(u, v) << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	almost_line_00	AC	506 ms	11 MB
g++-13	almost_line_01	AC	513 ms	11 MB
g++-13	binary_00	AC	870 ms	11 MB
g++-13	binary_01	AC	870 ms	11 MB
g++-13	binary_02	AC	931 ms	11 MB
g++-13	example_00	AC	5 ms	4 MB
g++-13	line_00	AC	397 ms	9 MB
g++-13	line_01	AC	408 ms	11 MB
g++-13	line_02	AC	280 ms	4 MB
g++-13	line_03	AC	57 ms	10 MB
g++-13	line_04	AC	107 ms	8 MB
g++-13	max_line_00	AC	495 ms	11 MB
g++-13	max_line_01	AC	490 ms	11 MB
g++-13	max_line_02	AC	489 ms	11 MB
g++-13	max_random_00	AC	608 ms	11 MB
g++-13	max_random_01	AC	621 ms	11 MB
g++-13	max_random_02	AC	645 ms	11 MB
g++-13	path_graph_root_centroid_00	AC	495 ms	11 MB
g++-13	path_graph_root_centroid_01	AC	497 ms	11 MB
g++-13	path_graph_root_centroid_02	AC	497 ms	11 MB
g++-13	random_00	AC	504 ms	10 MB
g++-13	random_01	AC	510 ms	11 MB
g++-13	random_02	AC	277 ms	4 MB
g++-13	random_03	AC	173 ms	10 MB
g++-13	random_04	AC	175 ms	8 MB
clang++-18	almost_line_00	AC	533 ms	11 MB
clang++-18	almost_line_01	AC	527 ms	11 MB
clang++-18	binary_00	AC	930 ms	11 MB
clang++-18	binary_01	AC	942 ms	11 MB
clang++-18	binary_02	AC	926 ms	11 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	line_00	AC	420 ms	10 MB
clang++-18	line_01	AC	430 ms	11 MB
clang++-18	line_02	AC	289 ms	4 MB
clang++-18	line_03	AC	62 ms	10 MB
clang++-18	line_04	AC	114 ms	8 MB
clang++-18	max_line_00	AC	519 ms	11 MB
clang++-18	max_line_01	AC	516 ms	11 MB
clang++-18	max_line_02	AC	511 ms	11 MB
clang++-18	max_random_00	AC	628 ms	11 MB
clang++-18	max_random_01	AC	621 ms	11 MB
clang++-18	max_random_02	AC	643 ms	11 MB
clang++-18	path_graph_root_centroid_00	AC	521 ms	11 MB
clang++-18	path_graph_root_centroid_01	AC	525 ms	11 MB
clang++-18	path_graph_root_centroid_02	AC	525 ms	11 MB
clang++-18	random_00	AC	526 ms	10 MB
clang++-18	random_01	AC	566 ms	11 MB
clang++-18	random_02	AC	288 ms	4 MB
clang++-18	random_03	AC	186 ms	10 MB
clang++-18	random_04	AC	193 ms	8 MB

Back to top page