This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #include "../../union_find/weighted_union_find.hpp" using namespace std; using llong = long long; struct A { using T = llong; using value_type = T; static inline T identity() { return 0; }; static inline T operation(T x, T y) { return x + y; }; static inline T inverse(T x) { return -x; }; }; llong n, q; llong com, x, y, w; int main() { cin >> n >> q; WeightedUnionFind<A> uf(n); while (q--) { cin >> com; if (com == 0) { cin >> x >> y >> w; uf.unite(x, y, w); } else { cin >> x >> y; if (uf.same(x, y)) { cout << uf.diff(x, y) << '\n'; } else { cout << "?\n"; } } } return 0; };
#line 1 "test/aoj/DSL1B.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #line 1 "union_find/weighted_union_find.hpp" #line 4 "union_find/weighted_union_find.hpp" //=== template <class Abel> struct WeightedUnionFind { using T = typename Abel::value_type; std::vector<int> parent; // [i] = i-th node's parent. if [i] < 0, i-th node is root. std::vector<T> diff_weight; // distance from parent WeightedUnionFind() = default; WeightedUnionFind(int nmemb) { init(nmemb); }; void init(int nmemb) { parent.resize(nmemb, -1); diff_weight.resize(nmemb, Abel::identity()); }; int root(int x) { if (parent[x] < 0) return x; int p = root(parent[x]); diff_weight[x] = Abel::operation(diff_weight[x], diff_weight[parent[x]]); parent[x] = p; return p; }; // unite x, y; weight(y) - weight(x) = w bool unite(int x, int y, T w) { T wx = weight(x); T wy = weight(y); x = root(x); y = root(y); if (x == y) return false; w = Abel::operation(w, wx); w = Abel::operation(w, Abel::inverse(wy)); if (size(x) < size(y)) std::swap(x, y), w = Abel::inverse(w); parent[x] += parent[y]; parent[y] = x; diff_weight[y] = w; return true; }; bool same(int x, int y) { return root(x) == root(y); }; T weight(int x) { root(x); return diff_weight[x]; }; T diff(int x, int y) { return Abel::operation(weight(y), Abel::inverse(weight(x))); }; int size(int x) { return -parent[root(x)]; }; }; //=== #line 19 "test/aoj/DSL1B.test.cpp" using namespace std; using llong = long long; struct A { using T = llong; using value_type = T; static inline T identity() { return 0; }; static inline T operation(T x, T y) { return x + y; }; static inline T inverse(T x) { return -x; }; }; llong n, q; llong com, x, y, w; int main() { cin >> n >> q; WeightedUnionFind<A> uf(n); while (q--) { cin >> com; if (com == 0) { cin >> x >> y >> w; uf.unite(x, y, w); } else { cin >> x >> y; if (uf.same(x, y)) { cout << uf.diff(x, y) << '\n'; } else { cout << "?\n"; } } } return 0; };