Submission #2338382


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)
#define MAX 200000

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

struct UnionFind {
    //number of parents(par[i] = i => root)
    vector <int> par;
    //rank of tree
    vector <int> rank;

    UnionFind(int n) : par(n), rank(n, 1) {
        //initialize
        rep(n, i) par[i] = i;
    }

    //find root (keiroasshuku at the same time)
    int root(int x){
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    //unite
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (rank[x] > rank[y]) swap(x, y);
        par[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }

    //same tree?
    bool same(int x, int y){
        return root(x) == root(y);
    }
};

/*
//number of elements
const int MAX_NODE = 100000;
//number of parents(par[i] = i => root)
int par[MAX_NODE];
//initialize
void init(int n){
    rep(n, i) par[i] = i;
}
//solve root
int root(int x){
    if (par[x] == x) return x;
    else return par[x] = root(par[x]);
}
//unit?
bool same(int x, int y){
    return root(x) == root(y);
}
//unite
void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x == y) return;
    par[x] = y;
}*/

void solve(void){
    int N, Q;
    cin >> N >> Q;
    UnionFind uf(N);
    rep(Q, meaningless){
        int p, a, b;
        scanf("%d %d %d\n", &p, &a, &b);
        if (p == 0) uf.unite(a, b);
        else if (p == 1) {
            printf("%s\n", uf.same(a, b)?"Yes":"No");
        }
    }
}

int main(void){
  solve();
  return 0;
}

Submission Info

Submission Time
Task B - Union Find
User sifi_border
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2326 Byte
Status AC
Exec Time 53 ms
Memory 1664 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:97:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d\n", &p, &a, &b);
                                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 1 ms 256 KB
subtask_01_01.txt AC 31 ms 640 KB
subtask_01_02.txt AC 2 ms 1024 KB
subtask_01_03.txt AC 44 ms 1024 KB
subtask_01_04.txt AC 52 ms 1664 KB
subtask_01_05.txt AC 4 ms 256 KB
subtask_01_06.txt AC 5 ms 1024 KB
subtask_01_07.txt AC 48 ms 768 KB
subtask_01_08.txt AC 53 ms 1664 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 2 ms 1024 KB
subtask_01_11.txt AC 47 ms 896 KB
subtask_01_12.txt AC 52 ms 1664 KB
subtask_01_13.txt AC 39 ms 768 KB
subtask_01_14.txt AC 2 ms 1024 KB
subtask_01_15.txt AC 47 ms 896 KB
subtask_01_16.txt AC 53 ms 1664 KB
subtask_01_17.txt AC 52 ms 1408 KB
subtask_01_18.txt AC 51 ms 1408 KB