Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: test/yukicoder/529.LCT.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/529
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "src/Graph/Graph.hpp"
#include "src/Graph/IncrementalBridgeConnectivity.hpp"
#include "src/DataStructure/LinkCutTree.hpp"
using namespace std;
struct RmaxQ {
 using T= pair<long long, int>;
 static T op(const T &vl, const T &vr) { return vl.first > vr.first ? vl : vr; }
 using commute= void;
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, Q;
 cin >> N >> M >> Q;
 Graph g(N, M);
 for (int i= 0; i < M; ++i) cin >> g[i], --g[i];
 IncrementalBridgeConnectivity ibc(N);
 for (auto [u, v]: g) ibc.add_edge(u, v);

 vector<int> id(N);
 int n= 0;
 for (int i= 0; i < N; ++i)
  if (i == ibc.leader(i)) id[i]= n++;

 LinkCutTree<RmaxQ> lct(n);
 for (int i= 0; i < n; i++) lct.set(i, {-1, i});
 for (auto [u, v]: g) {
  u= id[ibc.leader(u)], v= id[ibc.leader(v)];
  if (u == v) continue;
  lct.link(u, v);
 }

 priority_queue<long long> pq[n];
 for (int v= n; v--;) pq[v].push(-1);
 while (Q--) {
  int op, x, y;
  cin >> op >> x >> y;
  if (op == 1) {
   int u= id[ibc.leader(--x)];
   pq[u].push(y);
   lct.set(u, make_pair(pq[u].top(), u));
  } else {
   int u= id[ibc.leader(--x)], v= id[ibc.leader(--y)];
   auto [ans, w]= lct.prod(u, v);
   cout << ans << '\n';
   if (ans != -1) {
    pq[w].pop();
    lct.set(w, make_pair(pq[w].top(), w));
   }
  }
 }
 return 0;
}
#line 1 "test/yukicoder/529.LCT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/529
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#line 4 "src/Internal/ListRange.hpp"
#include <iterator>
#include <type_traits>
#define _LR(name, IT, CT) \
 template <class T> struct name { \
  using Iterator= typename std::vector<T>::IT; \
  Iterator bg, ed; \
  Iterator begin() const { return bg; } \
  Iterator end() const { return ed; } \
  size_t size() const { return std::distance(bg, ed); } \
  CT &operator[](int i) const { return bg[i]; } \
 }
_LR(ListRange, iterator, T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
 std::vector<T> dat;
 std::vector<int> p;
 size_t size() const { return p.size() - 1; }
 ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
 ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
 os << '[';
 for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
 return os << ']';
}
#line 3 "src/Graph/Graph.hpp"
struct Edge: std::pair<int, int> {
 using std::pair<int, int>::pair;
 Edge &operator--() { return --first, --second, *this; }
 int to(int v) const { return first ^ second ^ v; }
 friend std::istream &operator>>(std::istream &is, Edge &e) { return is >> e.first >> e.second, is; }
};
struct Graph: std::vector<Edge> {
 size_t n;
 Graph(size_t n= 0, size_t m= 0): vector(m), n(n) {}
 size_t vertex_size() const { return n; }
 size_t edge_size() const { return size(); }
 size_t add_vertex() { return n++; }
 size_t add_edge(int s, int d) { return emplace_back(s, d), size() - 1; }
 size_t add_edge(Edge e) { return emplace_back(e), size() - 1; }
#define _ADJ_FOR(a, b) \
 for (auto [u, v]: *this) a; \
 for (size_t i= 0; i < n; ++i) p[i + 1]+= p[i]; \
 for (int i= size(); i--;) { \
  auto [u, v]= (*this)[i]; \
  b; \
 }
#define _ADJ(a, b) \
 vector<int> p(n + 1), c(size() << !dir); \
 if (!dir) { \
  _ADJ_FOR((++p[u], ++p[v]), (c[--p[u]]= a, c[--p[v]]= b)) \
 } else if (dir > 0) { \
  _ADJ_FOR(++p[u], c[--p[u]]= a) \
 } else { \
  _ADJ_FOR(++p[v], c[--p[v]]= b) \
 } \
 return {c, p}
 CSRArray<int> adjacency_vertex(int dir) const { _ADJ(v, u); }
 CSRArray<int> adjacency_edge(int dir) const { _ADJ(i, i); }
#undef _ADJ
#undef _ADJ_FOR
};
#line 2 "src/Graph/IncrementalBridgeConnectivity.hpp"
#include <utility>
#line 4 "src/Graph/IncrementalBridgeConnectivity.hpp"
class IncrementalBridgeConnectivity {
 std::vector<int> cp, bp, bbf, z;
 int t;
 inline int crt(int v) { return cp[v] < 0 ? v : cp[v]= crt(cp[v]); }
 inline int par(int v) { return bbf[v] < 0 ? -1 : leader(bbf[v]); }
public:
 IncrementalBridgeConnectivity(int n): cp(n, -1), bp(n, -1), bbf(n, -1), z(n), t(0) {}
 inline int leader(int v) { return bp[v] < 0 ? v : bp[v]= leader(bp[v]); }
 int size(int v) { return -bp[leader(v)]; }
 bool two_edge_connected(int u, int v) { return leader(u) == leader(v); }
 bool connected(int u, int v) { return crt(u) == crt(v); }
 void add_edge(int u, int v) {
  int a= crt(u= leader(u)), b= crt(v= leader(v));
  if (a == b)
   for (++t, a= u, b= v;;) {
    if (z[a] == t) {
     for (int w: {u, v})
      for (int p; w= leader(w), w != a; bp[a]+= bp[w], bp[w]= a, w= p)
       if (p= bbf[w], bbf[w]= bbf[a]; bp[a] > bp[w]) std::swap(w, a);
     return;
    }
    if (z[a]= t, a= par(a); b != -1) std::swap(a, b);
   }
  if (cp[a] < cp[b]) std::swap(u, v), cp[a]+= cp[b], cp[b]= a;
  else cp[b]+= cp[a], cp[a]= b;
  for (int p; u != -1; u= p) p= par(u), bbf[u]= v, v= u;
 }
};
#line 4 "src/DataStructure/LinkCutTree.hpp"
#include <string>
#include <cstddef>
#line 7 "src/DataStructure/LinkCutTree.hpp"
#include <cassert>
#line 3 "src/Internal/detection_idiom.hpp"
#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 11 "test/yukicoder/529.LCT.test.cpp"
using namespace std;
struct RmaxQ {
 using T= pair<long long, int>;
 static T op(const T &vl, const T &vr) { return vl.first > vr.first ? vl : vr; }
 using commute= void;
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, Q;
 cin >> N >> M >> Q;
 Graph g(N, M);
 for (int i= 0; i < M; ++i) cin >> g[i], --g[i];
 IncrementalBridgeConnectivity ibc(N);
 for (auto [u, v]: g) ibc.add_edge(u, v);

 vector<int> id(N);
 int n= 0;
 for (int i= 0; i < N; ++i)
  if (i == ibc.leader(i)) id[i]= n++;

 LinkCutTree<RmaxQ> lct(n);
 for (int i= 0; i < n; i++) lct.set(i, {-1, i});
 for (auto [u, v]: g) {
  u= id[ibc.leader(u)], v= id[ibc.leader(v)];
  if (u == v) continue;
  lct.link(u, v);
 }

 priority_queue<long long> pq[n];
 for (int v= n; v--;) pq[v].push(-1);
 while (Q--) {
  int op, x, y;
  cin >> op >> x >> y;
  if (op == 1) {
   int u= id[ibc.leader(--x)];
   pq[u].push(y);
   lct.set(u, make_pair(pq[u].top(), u));
  } else {
   int u= id[ibc.leader(--x)], v= id[ibc.leader(--y)];
   auto [ans, w]= lct.prod(u, v);
   cout << ans << '\n';
   if (ans != -1) {
    pq[w].pop();
    lct.set(w, make_pair(pq[w].top(), w));
   }
  }
 }
 return 0;
}

Test cases

Env Name Status Elapsed Memory
g++-13 01_sample1.txt :heavy_check_mark: AC 8 ms 3 MB
g++-13 01_sample2.txt :heavy_check_mark: AC 6 ms 4 MB
g++-13 02_handmake1.txt :heavy_check_mark: AC 6 ms 4 MB
g++-13 02_handmake2.txt :heavy_check_mark: AC 6 ms 4 MB
g++-13 03_random1.txt :heavy_check_mark: AC 7 ms 4 MB
g++-13 03_random2.txt :heavy_check_mark: AC 7 ms 4 MB
g++-13 03_random3.txt :heavy_check_mark: AC 7 ms 4 MB
g++-13 03_random4.txt :heavy_check_mark: AC 7 ms 4 MB
g++-13 04_random1.txt :heavy_check_mark: AC 81 ms 8 MB
g++-13 04_random2.txt :heavy_check_mark: AC 83 ms 9 MB
g++-13 04_random3.txt :heavy_check_mark: AC 113 ms 15 MB
g++-13 04_random4.txt :heavy_check_mark: AC 117 ms 15 MB
g++-13 05_bomb1.txt :heavy_check_mark: AC 100 ms 8 MB
g++-13 05_bomb2.txt :heavy_check_mark: AC 195 ms 19 MB
g++-13 06_bomb1.txt :heavy_check_mark: AC 74 ms 7 MB
g++-13 07_random1.txt :heavy_check_mark: AC 305 ms 18 MB
g++-13 07_random2.txt :heavy_check_mark: AC 307 ms 18 MB
g++-13 99_system_test1.txt :heavy_check_mark: AC 326 ms 17 MB
g++-13 99_system_test2.txt :heavy_check_mark: AC 315 ms 17 MB
g++-13 99_system_test3.txt :heavy_check_mark: AC 318 ms 17 MB
clang++-18 01_sample1.txt :heavy_check_mark: AC 7 ms 4 MB
clang++-18 01_sample2.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 02_handmake1.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 02_handmake2.txt :heavy_check_mark: AC 6 ms 4 MB
clang++-18 03_random1.txt :heavy_check_mark: AC 7 ms 4 MB
clang++-18 03_random2.txt :heavy_check_mark: AC 7 ms 4 MB
clang++-18 03_random3.txt :heavy_check_mark: AC 7 ms 4 MB
clang++-18 03_random4.txt :heavy_check_mark: AC 7 ms 4 MB
clang++-18 04_random1.txt :heavy_check_mark: AC 83 ms 8 MB
clang++-18 04_random2.txt :heavy_check_mark: AC 83 ms 9 MB
clang++-18 04_random3.txt :heavy_check_mark: AC 108 ms 14 MB
clang++-18 04_random4.txt :heavy_check_mark: AC 115 ms 15 MB
clang++-18 05_bomb1.txt :heavy_check_mark: AC 92 ms 8 MB
clang++-18 05_bomb2.txt :heavy_check_mark: AC 163 ms 19 MB
clang++-18 06_bomb1.txt :heavy_check_mark: AC 77 ms 7 MB
clang++-18 07_random1.txt :heavy_check_mark: AC 307 ms 18 MB
clang++-18 07_random2.txt :heavy_check_mark: AC 299 ms 18 MB
clang++-18 99_system_test1.txt :heavy_check_mark: AC 281 ms 17 MB
clang++-18 99_system_test2.txt :heavy_check_mark: AC 280 ms 17 MB
clang++-18 99_system_test3.txt :heavy_check_mark: AC 282 ms 17 MB
Back to top page