This documentation is automatically generated by online-judge-tools/verification-helper
#include "ds/unionfind/rollback_weighted_unionfind.hpp"
#include "ds/rollback_array.hpp"
template <typename Group>
struct Rollback_Weighted_UnionFind {
using E = typename Group::value_type;
using P = pair<int, E>;
Rollback_Array<P> dat; // parent or -size
Rollback_Weighted_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_weighted_unionfind.hpp"
template <typename Group>
struct Rollback_Weighted_UnionFind {
using E = typename Group::value_type;
using P = pair<int, E>;
Rollback_Array<P> dat; // parent or -size
Rollback_Weighted_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;
}
};