src/test/aoj_DSL_1_A.cpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#include "../dsu.hpp"
int main() {
    int n, q;
    cin >> n >> q;
    dsu uf(n);
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            uf.merge(x, y);
        }
        else {
            cout << uf.same(x, y) << "\n";
        }
    }
}

#line 1 "src/test/aoj_DSL_1_A.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/dsu.hpp"

struct dsu {
    vector<int> p;
    dsu(int n): p(n, -1) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int leader(int a) { return p[a] < 0 ? a : p[a] = leader(p[a]); }
    int size(int a) { return -p[leader(a)]; }
    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return a;
    }
};
#line 4 "src/test/aoj_DSL_1_A.cpp"
int main() {
    int n, q;
    cin >> n >> q;
    dsu uf(n);
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            uf.merge(x, y);
        }
        else {
            cout << uf.same(x, y) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	5 ms	4 MB
g++	00_small_01.in	AC	4 ms	4 MB
g++	01_rand_00.in	AC	4 ms	4 MB
g++	01_rand_01.in	AC	4 ms	4 MB
g++	01_rand_02.in	AC	4 ms	4 MB
g++	01_rand_03.in	AC	4 ms	4 MB
g++	01_rand_04.in	AC	4 ms	4 MB
g++	01_rand_05.in	AC	4 ms	4 MB
g++	02_linear_00.in	AC	4 ms	4 MB
g++	02_linear_01.in	AC	5 ms	4 MB
g++	02_linear_02.in	AC	6 ms	4 MB
g++	02_linear_03.in	AC	8 ms	4 MB
g++	03_grid_00.in	AC	5 ms	4 MB
g++	03_grid_01.in	AC	4 ms	4 MB
g++	03_grid_02.in	AC	4 ms	4 MB
g++	03_grid_03.in	AC	5 ms	4 MB
g++	03_grid_04.in	AC	5 ms	4 MB
g++	03_grid_05.in	AC	4 ms	4 MB
g++	03_grid_06.in	AC	4 ms	4 MB
g++	03_grid_07.in	AC	4 ms	4 MB
g++	03_grid_08.in	AC	5 ms	4 MB
g++	04_critical_00.in	AC	7 ms	4 MB
g++	04_critical_01.in	AC	8 ms	4 MB
g++	05_groups_00.in	AC	12 ms	4 MB
g++	05_groups_01.in	AC	12 ms	4 MB
g++	05_groups_02.in	AC	12 ms	4 MB
g++	05_groups_03.in	AC	12 ms	4 MB
g++	05_groups_04.in	AC	12 ms	4 MB
g++	06_randmax_00.in	AC	5 ms	4 MB
g++	06_randmax_01.in	AC	13 ms	4 MB
g++	06_randmax_02.in	AC	16 ms	4 MB
g++	06_randmax_03.in	AC	21 ms	4 MB
clang++	00_small_00.in	AC	5 ms	4 MB
clang++	00_small_01.in	AC	5 ms	4 MB
clang++	01_rand_00.in	AC	5 ms	4 MB
clang++	01_rand_01.in	AC	5 ms	4 MB
clang++	01_rand_02.in	AC	5 ms	4 MB
clang++	01_rand_03.in	AC	4 ms	4 MB
clang++	01_rand_04.in	AC	5 ms	4 MB
clang++	01_rand_05.in	AC	5 ms	4 MB
clang++	02_linear_00.in	AC	5 ms	4 MB
clang++	02_linear_01.in	AC	5 ms	4 MB
clang++	02_linear_02.in	AC	6 ms	4 MB
clang++	02_linear_03.in	AC	8 ms	4 MB
clang++	03_grid_00.in	AC	5 ms	4 MB
clang++	03_grid_01.in	AC	5 ms	4 MB
clang++	03_grid_02.in	AC	5 ms	4 MB
clang++	03_grid_03.in	AC	5 ms	4 MB
clang++	03_grid_04.in	AC	5 ms	4 MB
clang++	03_grid_05.in	AC	5 ms	4 MB
clang++	03_grid_06.in	AC	5 ms	4 MB
clang++	03_grid_07.in	AC	5 ms	4 MB
clang++	03_grid_08.in	AC	5 ms	4 MB
clang++	04_critical_00.in	AC	8 ms	4 MB
clang++	04_critical_01.in	AC	8 ms	4 MB
clang++	05_groups_00.in	AC	13 ms	4 MB
clang++	05_groups_01.in	AC	13 ms	4 MB
clang++	05_groups_02.in	AC	13 ms	4 MB
clang++	05_groups_03.in	AC	13 ms	4 MB
clang++	05_groups_04.in	AC	12 ms	4 MB
clang++	06_randmax_00.in	AC	6 ms	4 MB
clang++	06_randmax_01.in	AC	13 ms	4 MB
clang++	06_randmax_02.in	AC	17 ms	4 MB
clang++	06_randmax_03.in	AC	22 ms	4 MB