This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "ds/unionfind/rollback_potentialized_unionfind.hpp"
#include "ds/rollback_array.hpp" template <typename Group> struct Rollback_Potentialized_UnionFind { using E = typename Group::value_type; using P = pair<int, E>; Rollback_Array<P> dat; // parent or -size Rollback_Potentialized_UnionFind(int n) : dat(vc<P>(n, P(-1, Group::unit()))) {} P get(int v) { // 経路圧縮はしないように E val = Group::unit(); while (1) { auto [p, x] = dat.get(v); if (p < 0) { break; } val = Group::op(x, val); v = p; } return {v, val}; } int time() { return dat.time(); } void rollback(int t) { dat.rollback(t); } bool merge(int a, int b, E x) { auto [v1, x1] = get(a); auto [v2, x2] = get(b); if (v1 == v2) return false; int s1 = -dat.get(v1).fi; int s2 = -dat.get(v2).fi; if (s1 < s2) { swap(s1, s2), swap(v1, v2), swap(x1, x2); x = Group::inverse(x); } // v1 <- v2 x = Group::op(x1, x); x = Group::op(x, Group::inverse(x2)); dat.set(v2, P({v1, x})); dat.set(v1, P({-(s1 + s2), Group::unit()})); return true; } };
#line 2 "ds/rollback_array.hpp" template <typename T> struct Rollback_Array { int N; vc<T> dat; vc<pair<int, T>> history; Rollback_Array() {} Rollback_Array(vc<T> x) : N(len(x)), dat(x) {} Rollback_Array(int N) : N(N), dat(N) {} template <typename F> Rollback_Array(int N, F f) : N(N) { dat.reserve(N); FOR(i, N) dat.eb(f(i)); } int time() { return len(history); } void rollback(int t) { FOR_R(i, t, time()) { auto& [idx, v] = history[i]; dat[idx] = v; } history.resize(t); } T get(int idx) { return dat[idx]; } void set(int idx, T x) { history.eb(idx, dat[idx]); dat[idx] = x; } vc<T> get_all() { vc<T> res(N); FOR(i, N) res[i] = get(i); return res; } }; #line 2 "ds/unionfind/rollback_potentialized_unionfind.hpp" template <typename Group> struct Rollback_Potentialized_UnionFind { using E = typename Group::value_type; using P = pair<int, E>; Rollback_Array<P> dat; // parent or -size Rollback_Potentialized_UnionFind(int n) : dat(vc<P>(n, P(-1, Group::unit()))) {} P get(int v) { // 経路圧縮はしないように E val = Group::unit(); while (1) { auto [p, x] = dat.get(v); if (p < 0) { break; } val = Group::op(x, val); v = p; } return {v, val}; } int time() { return dat.time(); } void rollback(int t) { dat.rollback(t); } bool merge(int a, int b, E x) { auto [v1, x1] = get(a); auto [v2, x2] = get(b); if (v1 == v2) return false; int s1 = -dat.get(v1).fi; int s2 = -dat.get(v2).fi; if (s1 < s2) { swap(s1, s2), swap(v1, v2), swap(x1, x2); x = Group::inverse(x); } // v1 <- v2 x = Group::op(x1, x); x = Group::op(x, Group::inverse(x2)); dat.set(v2, P({v1, x})); dat.set(v1, P({-(s1 + s2), Group::unit()})); return true; } };