This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#include "../potentialized_unionfind.hpp" #include <iostream> #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp" using namespace std; int main() { int N, Q, x, y, z; cin >> N >> Q; PotentializedUnionFind<int> uf(N); for (int i = 0; i < Q; i++) { int c; cin >> c; if (c) { cin >> x >> y; if (uf.same(x, y)) { cout << uf.diff(x, y) << endl; } else { cout << "?" << endl; } } else { cin >> x >> y >> z; uf.unite(x, y, z); } } }
#line 2 "unionfind/potentialized_unionfind.hpp" #include <numeric> #include <utility> #include <vector> // Potentialized UnionFind (Weighted UnionFind) template <class S> struct PotentializedUnionFind { std::vector<int> par, sz; std::vector<S> pot; PotentializedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) { std::iota(par.begin(), par.end(), 0); } int find(int x) { if (par[x] != x) { int r = find(par[x]); pot[x] = pot[x] + pot[par[x]], par[x] = r; } return par[x]; } bool unite(int s, int t, S rel_diff) { // Relate s and t by f[t] = f[s] + rel_diff // Return false iff contradiction happens. rel_diff = rel_diff + weight(s) + (-weight(t)); if ((s = find(s)) == (t = find(t))) return rel_diff == 0; if (sz[s] < sz[t]) std::swap(s, t), rel_diff = -rel_diff; par[t] = s, sz[s] += sz[t], pot[t] = rel_diff; return true; } S weight(int x) { return find(x), pot[x]; } S diff(int s, int t) { return weight(t) + (-weight(s)); } // return f[t] - f[s] int count(int x) { return sz[find(x)]; } bool same(int s, int t) { return find(s) == find(t); } }; #line 2 "unionfind/test/potentialized_unionfind.test.cpp" #include <iostream> #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp" using namespace std; int main() { int N, Q, x, y, z; cin >> N >> Q; PotentializedUnionFind<int> uf(N); for (int i = 0; i < Q; i++) { int c; cin >> c; if (c) { cin >> x >> y; if (uf.same(x, y)) { cout << uf.diff(x, y) << endl; } else { cout << "?" << endl; } } else { cin >> x >> y >> z; uf.unite(x, y, z); } } }