sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B" #include "../../data-structure/unionfind/weighted_union_find.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; WeightedUnionFind<int> wuf(n); for (int i = 0; i < q; i++) { int t; cin >> t; if (t == 0) { int x, y, z; cin >> x >> y >> z; wuf.unite(x, y, z); } else { int x, y; cin >> x >> y; if (wuf.same(x, y)) cout << wuf.diff(x, y) << "\n"; else cout << "?\n"; } } }
#line 1 "test/aoj/DSL_1_B.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B" #line 2 "data-structure/unionfind/weighted_union_find.hpp" #include <algorithm> #include <vector> template <typename T> class WeightedUnionFind { public: WeightedUnionFind() = default; explicit WeightedUnionFind(int n) : data(n, -1), ws(n) {} int find(int x) { if (data[x] < 0) return x; int r = find(data[x]); ws[x] += ws[data[x]]; return data[x] = r; } T weight(int x) { find(x); return ws[x]; } bool unite(int x, int y, T w) { w += weight(x); w -= weight(y); x = find(x); y = find(y); if (x == y) return false; if (data[x] > data[y]) { std::swap(x, y); w = -w; } data[x] += data[y]; data[y] = x; ws[y] = w; return true; } bool same(int x, int y) { return find(x) == find(y); } T diff(int x, int y) { return weight(y) - weight(x); } int size(int x) { return -data[find(x)]; } private: std::vector<int> data; std::vector<T> ws; }; #line 4 "test/aoj/DSL_1_B.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; WeightedUnionFind<int> wuf(n); for (int i = 0; i < q; i++) { int t; cin >> t; if (t == 0) { int x, y, z; cin >> x >> y >> z; wuf.unite(x, y, z); } else { int x, y; cin >> x >> y; if (wuf.same(x, y)) cout << wuf.diff(x, y) << "\n"; else cout << "?\n"; } } }