This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/data-structure/disjoint-set-union.hpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; DisjointSetUnion d(n); for ([[maybe_unused]] usize _: rep(0, q)) { usize com, x, y; std::cin >> com >> x >> y; if (not com) { d.merge(x, y); } else { std::cout << (d.same(x, y)) << std::endl; } } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/aoj/dsl_1_a.test.cpp" // verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/data-structure/disjoint-set-union.hpp" #line 5 "src/data-structure/disjoint-set-union.hpp" #line 7 "src/data-structure/disjoint-set-union.hpp" #include <cassert> #include <vector> namespace luz { class DisjointSetUnion { usize n; // vals[v] := // if v is root node: -1 * component size // otherwise: parent node std::vector< isize > vals; void bound_check(usize v) const { assert(v < n); } usize impl_leader(usize v) { if (vals[v] < 0) return v; return vals[v] = leader(vals[v]); } public: DisjointSetUnion() = default; explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {} usize size() const { return n; } usize leader(usize v) { bound_check(v); return impl_leader(v); } bool same(usize u, usize v) { bound_check(u), bound_check(v); return impl_leader(u) == impl_leader(v); } usize merge(usize u, usize v) { bound_check(u); bound_check(v); isize x = impl_leader(u); isize y = impl_leader(v); if (x == y) return x; if (-vals[x] < -vals[y]) std::swap(x, y); vals[x] += vals[y]; vals[y] = x; return x; } usize group_size(usize v) { bound_check(v); return -vals[impl_leader(v)]; } std::vector< std::vector< usize > > groups() { std::vector< std::vector< usize > > result(n); std::vector< usize > leaders(n), g_sizes(n); for (usize v: rep(0, n)) { leaders[v] = impl_leader(v); g_sizes[leaders[v]]++; } for (usize v: rep(0, n)) { result[v].reserve(g_sizes[v]); } for (usize v: rep(0, n)) { result[leaders[v]].emplace_back(v); } auto empty_check = [](const std::vector< usize > &vs) { return vs.empty(); }; result.erase( std::remove_if(result.begin(), result.end(), empty_check), result.end()); return result; } }; } // namespace luz #line 6 "test/aoj/dsl_1_a.test.cpp" #include <iostream> namespace luz { void main_() { usize n, q; std::cin >> n >> q; DisjointSetUnion d(n); for ([[maybe_unused]] usize _: rep(0, q)) { usize com, x, y; std::cin >> com >> x >> y; if (not com) { d.merge(x, y); } else { std::cout << (d.same(x, y)) << std::endl; } } } } // namespace luz int main() { luz::main_(); }