Hashiryo's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/sample_test/typical90_bp.UFPU.test.cpp
- View this file on GitHub
- Last update: 2024-09-21 22:51:54+09:00
- Link: https://atcoder.jp/contests/typical90/tasks/typical90_bp
Depends on
- Union-Find (ポテンシャル, undo可能) (src/DataStructure/UnionFind_Potentialized_Undoable.hpp)
detection idiom (src/Internal/detection_idiom.hpp)- 代数的構造 (src/Math/Algebra.hpp)
Code
// competitive-verifier: STANDALONE
// https://atcoder.jp/contests/typical90/tasks/typical90_bp
// ポテンシャルUF (affine 合成, 非可換群)
#include <sstream>
#include <string>
#include <cassert>
#include "src/DataStructure/UnionFind_Potentialized_Undoable.hpp"
#include "src/Math/Algebra.hpp"
using namespace std;
bool test(int (*solve)(stringstream &, stringstream &), string in, string expected) {
stringstream scin(in), scout;
solve(scin, scout);
return scout.str() == expected;
}
namespace TEST {
struct M {
using T= pair<bool, long long>;
static constexpr T o= {false, 0};
static T add(const T &a, const T &b) {
if (b.first) return {!a.first, b.second - a.second};
else return {a.first, a.second + b.second};
}
static T neg(const T &a) { return {a.first, (a.first ? a.second : -a.second)}; }
};
signed main(stringstream &scin, stringstream &scout) {
using G= Algebra<M>;
int N, Q;
scin >> N >> Q;
UnionFind_Potentialized_Undoable<G> uf(N);
while (Q--) {
int T, X, Y, V;
scin >> T >> X >> Y >> V, --X, --Y;
if (T) {
if (uf.connected(X, Y)) {
auto [a, b]= uf.diff(Y, X).x;
scout << (a ? -V : V) + b << '\n';
} else scout << "Ambiguous" << '\n';
} else {
uf.unite(Y, X, G(make_pair(true, V)));
}
}
return 0;
}
}
signed main() {
assert(test(TEST::main,
"4\n"
"7\n"
"0 1 2 3\n"
"1 1 2 1\n"
"1 3 4 5\n"
"0 3 4 6\n"
"1 3 4 5\n"
"0 2 3 6\n"
"1 3 1 5\n",
"2\n"
"Ambiguous\n"
"1\n"
"2\n"));
assert(test(TEST::main,
"15\n"
"25\n"
"0 11 12 41\n"
"0 1 2 159\n"
"0 14 15 121\n"
"0 4 5 245\n"
"0 12 13 157\n"
"0 9 10 176\n"
"0 6 7 170\n"
"0 2 3 123\n"
"0 7 8 167\n"
"0 3 4 159\n"
"1 12 11 33\n"
"0 10 11 116\n"
"0 8 9 161\n"
"1 9 12 68\n"
"1 12 12 33\n"
"1 7 12 74\n"
"0 5 6 290\n"
"1 8 9 93\n"
"0 13 14 127\n"
"1 10 12 108\n"
"1 14 1 3\n"
"1 13 8 124\n"
"1 12 11 33\n"
"1 12 10 33\n"
"1 5 15 194\n",
"8\n"
"33\n"
"33\n"
"33\n"
"68\n"
"33\n"
"144\n"
"93\n"
"8\n"
"108\n"
"118\n"));
return 0;
}#line 1 "test/sample_test/typical90_bp.UFPU.test.cpp"
// competitive-verifier: STANDALONE
// https://atcoder.jp/contests/typical90/tasks/typical90_bp
// ポテンシャルUF (affine 合成, 非可換群)
#include <sstream>
#include <string>
#include <cassert>
#line 2 "src/DataStructure/UnionFind_Potentialized_Undoable.hpp"
#include <vector>
#include <algorithm>
#line 5 "src/DataStructure/UnionFind_Potentialized_Undoable.hpp"
template <class weight_t> class UnionFind_Potentialized_Undoable {
std::vector<int> par;
std::vector<weight_t> val;
std::vector<std::tuple<int, int, weight_t, int>> his;
int cur;
public:
UnionFind_Potentialized_Undoable(int n): par(n, -1), val(n), his{{-1, -1, weight_t(), 1}}, cur(0) { his.reserve(n + 1); }
int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
// -p(v) + p(u) = w
bool unite(int u, int v, weight_t w) {
if constexpr (std::is_same_v<weight_t, bool>) w^= potential(v) ^ potential(u);
else w= potential(v) + w - potential(u);
if (++cur; (u= leader(u)) == (v= leader(v))) return ++std::get<3>(his.back()), w == weight_t();
if (par[v] > par[u]) std::swap(u, v), w= -w;
return his.emplace_back(u, par[u], val[u], 1), par[v]+= par[u], par[u]= v, val[u]= w, true;
}
bool connected(int u, int v) { return leader(u) == leader(v); }
int size(int u) { return -par[leader(u)]; }
weight_t potential(int u) {
if (par[u] < 0) return val[u];
if constexpr (std::is_same_v<weight_t, bool>) return potential(par[u]) ^ val[u];
else return potential(par[u]) + val[u];
}
// -p(v) + p(u)
weight_t diff(int u, int v) {
if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
else return -potential(v) + potential(u);
}
int time() const { return cur; }
void undo() {
if (assert(cur > 0), --cur; --std::get<3>(his.back()) == 0) {
auto [u, p, v, _]= his.back();
par[par[u]]-= p, par[u]= p, val[u]= v, his.pop_back();
}
}
void rollback(int t) {
assert(0 <= t), assert(t <= cur);
if (t == cur) return;
for (;;) {
auto &[u, p, v, i]= his.back();
if (cur-= i; cur < t) {
i= t - cur, cur= t;
break;
}
par[par[u]]-= p, par[u]= p, val[u]= v, his.pop_back();
}
}
};
#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 3 "src/Math/Algebra.hpp"
template <class M> struct Algebra {
using T= typename M::T;
_DETECT_BOOL(has_zero, decltype(T::o));
_DETECT_BOOL(has_one, decltype(T::i));
static inline T zero= has_zero_v<M> ? M::o : T();
static inline T one= has_one_v<M> ? M::i : T();
T x;
Algebra(): x(zero) {}
Algebra(bool y): x(y ? one : zero) {}
template <class U, typename= std::enable_if_t<std::is_convertible_v<U, T>>> Algebra(U y): x(y) {}
Algebra &operator+=(const Algebra &r) { return *this= *this + r; }
Algebra &operator-=(const Algebra &r) { return *this= *this - r; }
Algebra &operator*=(const Algebra &r) { return *this= *this * r; }
Algebra operator+(const Algebra &r) const { return Algebra(M::add(x, r.x)); }
Algebra operator-(const Algebra &r) const { return Algebra(M::add(x, M::neg(r.x))); }
Algebra operator*(const Algebra &r) const { return Algebra(M::mul(x, r.x)); }
Algebra operator-() const { return Algebra(M::neg(x)); }
bool operator==(const Algebra &r) const { return x == r.x; }
bool operator!=(const Algebra &r) const { return x != r.x; }
friend std::istream &operator>>(std::istream &is, Algebra &r) { return is >> r.x, is; }
friend std::ostream &operator<<(std::ostream &os, const Algebra &r) { return os << r.x; }
};
#line 10 "test/sample_test/typical90_bp.UFPU.test.cpp"
using namespace std;
bool test(int (*solve)(stringstream &, stringstream &), string in, string expected) {
stringstream scin(in), scout;
solve(scin, scout);
return scout.str() == expected;
}
namespace TEST {
struct M {
using T= pair<bool, long long>;
static constexpr T o= {false, 0};
static T add(const T &a, const T &b) {
if (b.first) return {!a.first, b.second - a.second};
else return {a.first, a.second + b.second};
}
static T neg(const T &a) { return {a.first, (a.first ? a.second : -a.second)}; }
};
signed main(stringstream &scin, stringstream &scout) {
using G= Algebra<M>;
int N, Q;
scin >> N >> Q;
UnionFind_Potentialized_Undoable<G> uf(N);
while (Q--) {
int T, X, Y, V;
scin >> T >> X >> Y >> V, --X, --Y;
if (T) {
if (uf.connected(X, Y)) {
auto [a, b]= uf.diff(Y, X).x;
scout << (a ? -V : V) + b << '\n';
} else scout << "Ambiguous" << '\n';
} else {
uf.unite(Y, X, G(make_pair(true, V)));
}
}
return 0;
}
}
signed main() {
assert(test(TEST::main,
"4\n"
"7\n"
"0 1 2 3\n"
"1 1 2 1\n"
"1 3 4 5\n"
"0 3 4 6\n"
"1 3 4 5\n"
"0 2 3 6\n"
"1 3 1 5\n",
"2\n"
"Ambiguous\n"
"1\n"
"2\n"));
assert(test(TEST::main,
"15\n"
"25\n"
"0 11 12 41\n"
"0 1 2 159\n"
"0 14 15 121\n"
"0 4 5 245\n"
"0 12 13 157\n"
"0 9 10 176\n"
"0 6 7 170\n"
"0 2 3 123\n"
"0 7 8 167\n"
"0 3 4 159\n"
"1 12 11 33\n"
"0 10 11 116\n"
"0 8 9 161\n"
"1 9 12 68\n"
"1 12 12 33\n"
"1 7 12 74\n"
"0 5 6 290\n"
"1 8 9 93\n"
"0 13 14 127\n"
"1 10 12 108\n"
"1 14 1 3\n"
"1 13 8 124\n"
"1 12 11 33\n"
"1 12 10 33\n"
"1 5 15 194\n",
"8\n"
"33\n"
"33\n"
"33\n"
"68\n"
"33\n"
"144\n"
"93\n"
"8\n"
"108\n"
"118\n"));
return 0;
}