Submit Info #2658

Problem Lang User Status Time Memory
Unionfind cpp null0124 AC 55 ms 3.63 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.63 MiB
random_00 AC 44 ms 2.62 MiB
random_01 AC 44 ms 3.00 MiB
random_02 AC 36 ms 1.46 MiB
random_03 AC 14 ms 3.13 MiB
random_04 AC 27 ms 0.88 MiB
random_05 AC 37 ms 1.50 MiB
random_06 AC 38 ms 3.63 MiB
random_07 AC 10 ms 2.03 MiB
random_08 AC 15 ms 0.75 MiB
random_09 AC 55 ms 2.40 MiB

/* このコード、と~おれ! Be accepted! ∧_∧  (。・ω・。)つ━☆・*。 ⊂   ノ    ・゜+.  しーJ   °。+ *´¨)          .· ´¸.·*´¨) ¸.·*¨)           (¸.·´ (¸.·'* ☆ */ #include <stdio.h> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <vector> #include <numeric> #include <iostream> #include <random> #include <map> #include <unordered_map> #include <queue> #include <regex> #include <functional> /*多倍長整数/cpp_intで宣言 #include <boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; */ #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define rep(i, n) for(int i = 0; i < (n); ++i) #define rep1(i, n) for(int i = 1; i <= (n); ++i) #define rep2(i, n) for(int i = 2; i < (n); ++i) #define repr(i, n) for(int i = n; i >= 0; --i) #define reprm(i, n) for(int i = n - 1; i >= 0; --i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printin(a) printf(a ? "possible\n" : "inposible\n") #define printdb(a) printf("%.50lf\n", a)//少数出力 #define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ) #define prints(s) printf("%s\n", s.c_str())//string出力 #define all(x) (x).begin(), (x).end() #define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数 #define pb push_back #define priq priority_queue #define rpriq priq<int, vector<int>, greater<int>> #define deg_to_rad(deg) (((deg)/360.0)*2.0*PI) #define rad_to_deg(rad) (((rad)/2.0/PI)*360.0) #define Please return #define AC 0 #define debug(aa, a) fprintf(stderr, aa, a) using ll =long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1000000007; const long double PI = acos(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c);//最初の改行対策 while (c != '\n' && c != -1) { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } ll lcm(ll number1, ll number2) {//lcmを求める return number1 / gcd(number1, number2) * number2; } /*-----------------------------------------ここからコード-----------------------------------------*/ struct unionfind {//0-indexed vector<ll> par, siz; unionfind(ll n) : par(n), siz(n) { for (ll i = 0; i < n; ++i) { par[i] = i;//全部根で初期化 siz[i] = 1;//サイズは1 } } void init(ll n) { par.resize(n); siz.resize(n); for (ll i = 0; i < n; ++i) { par[i] = i;//全部根で初期化 siz[i] = 1;//サイズは1 } } ll find(ll a) {//根を返す return par[a] == a ? a : par[a] = find(par[a]); } bool unite(ll a, ll b) {//くっつける。元から同じだったらfalseを返す ll x = find(a), y = find(b); if (x == y)return false; else if (siz[x] < siz[y]) { par[x] = y; siz[y] += siz[x]; } else if (siz[x] > siz[y]) { par[y] = x; siz[x] += siz[y]; } else { par[x] = y; siz[y] += siz[x]; } return true; } bool same(ll a, ll b) {//同じ集合か判定する return find(a) == find(b); } ll size(ll a) {//サイズを返す return siz[find(a)]; } vector<ll> leaf(ll a) {//同じ集合に属す葉を纏めて返す vector<ll> x; ll n = par.size(); for (ll i = 0; i < n; ++i)if (same(a, i))x.pb(i); return x; } }; int main() { int n, q; scanf("%d%d", &n, &q); int t, a, b; unionfind tree(n); rep(i, q) { scanf("%d%d%d", &t, &a, &b); if (t)printf("%d\n", tree.same(a, b)); else tree.unite(a, b); } Please AC; }