Submission #1177690

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <cstring>
#include <cctype>
#include <numeric>
#include <vector>

class FastScanner {
    static const size_t E=1<<17;
    static char*e,t[E|1],*a;
    static bool o(){size_t i=fread(t,1,E,stdin);t[i]=0;a=t+i;e=t;return i;}
public:
    FastScanner(){o();}
    template<class A>
    static void scan(A&i,typename std::enable_if<!std::is_signed<A>::value>::type*_=0){bool n=0;i=0;for(;;){char s=*e++;if(!s){if(!o())break;s=*e++;}if(s>='0'&&s<='9'){n=1;i=i*10+s-'0';}else if(n){break;}}}
    template<class A,class...O>
    static void scan(A&&i,O&&...n){scan(i),scan(n...);}
};

char FastScanner::t[],*FastScanner::e=t,*FastScanner::a=e+E;

class FastPrinter {
    static const size_t E=1<<17;
    static char*e,t[E|1],*a;
    static void o(){fwrite(t,1,e-t,stdout);e=t;}
public:
    static void print(const char*i){size_t n=strlen(i);char*s=e+n;if(s>=a){o();s=t+n;}if(n>=E){fwrite(i,1,n,stdout);return;}memcpy(e,i,n);e=s;}
    static void flush(){fwrite(t,1,e-t,stdout);fflush(stdout);e=t;}
    ~FastPrinter(){o();}
};

char FastPrinter::t[],*FastPrinter::e=t,*FastPrinter::a=t+E;

class UnionFindTree {
    std::vector<int> tree;
public:
    UnionFindTree(size_t n): tree(n, -1) {}
    size_t find_root(size_t v) {
        if (tree[v] < 0) return v;
        return tree[v] = find_root(tree[v]);
    }
    bool unite(size_t x, size_t y) {
        x = find_root(x);
        y = find_root(y);
        if (x == y) return false;
        if (tree[x] > tree[y]) std::swap(x, y);
        tree[x] += tree[y];
        tree[y] = x;
        return true;
    }
    bool connected(size_t x, size_t y) {
        return find_root(x) == find_root(y);
    }
    size_t rank(size_t v) {
        return -tree[find_root(v)];
    }
};

int main() {
    size_t N;
    unsigned Q;
    FastScanner::scan(N, Q);

    UnionFindTree tree(N);
    for (; Q--;) {
        unsigned P;
        size_t A, B;
        FastScanner::scan(P, A, B);

        if (P) {
            FastPrinter::print(tree.connected(A, B)? "Yes\n":"No\n");
        } else {
            tree.unite(A, B);
        }
    }

    FastPrinter::flush();
    return 0;
}

Submission Info

Judge Result