Submit Info #3593

Problem Lang User Status Time Memory
Unionfind cpp KoD AC 159 ms 1.42 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
random_00 AC 123 ms 1.31 MiB
random_01 AC 125 ms 1.39 MiB
random_02 AC 99 ms 0.91 MiB
random_03 AC 27 ms 1.30 MiB
random_04 AC 82 ms 0.80 MiB
random_05 AC 116 ms 0.92 MiB
random_06 AC 96 ms 1.42 MiB
random_07 AC 13 ms 1.05 MiB
random_08 AC 44 ms 0.74 MiB
random_09 AC 159 ms 1.25 MiB

#include <iostream> #include <algorithm> #include <utility> #include <vector> #include <numeric> #include <functional> #include <tuple> template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } // [l, r) from l to r struct range { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr l, r; constexpr range(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {} constexpr itr begin() const { return l; } constexpr itr end() const { return r; } }; // [l, r) from r to l struct revrange { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr r, l; constexpr revrange(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {} constexpr itr begin() const { return r; } constexpr itr end() const { return l; } }; template <class T> inline T scan() { T res; std::cin >> res; return res; } class union_find { private: int component; std::vector<int> parent; public: union_find() = default; union_find(int size_) { init(size_); } void init(int size_) { component = size_; parent.assign(size_, -1); } int count_components() const { return component; } int component_size(int i) { return -parent[find_parent(i)]; } bool same_component(int i, int j) { return find_parent(i) == find_parent(j); } int find_parent(int i) { if (parent[i] < 0) { return i; } else { return parent[i] = find_parent(parent[i]); } } bool unite(int i, int j) { i = find_parent(i); j = find_parent(j); if (i == j) { return true; } if (parent[i] > parent[j]) { std::swap(i, j); } parent[i] += parent[j]; parent[j] = i; --component; return true; } }; int main() { int N, Q; std::cin >> N >> Q; union_find uni(N); for (int i: range(0, Q)) { int t, u, v; std::cin >> t >> u >> v; if (t == 0) { uni.unite(u, v); } else { std::cout << uni.same_component(u, v) << '\n'; } } return 0; }