Submission #1172895


Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstddef>

class FastIO {
    // output buffer must be larger than each output
    static const size_t BUF_SIZE=1<<17;
    static char inbuf[BUF_SIZE|1], *inptr, *endinbuf;
    static char outbuf[BUF_SIZE|1], *outptr, *endoutbuf;
    static void weak_flush() {
        // flushes the internal buffer but not flushing stdout
        fwrite(outbuf, 1, outptr-outbuf, stdout);
        outptr = outbuf;
    }
    static void buffer() {
        // reads characters from stdin and buffers
        size_t len=fread(inbuf, 1, BUF_SIZE, stdin);
        inbuf[len] = '\0';
        inptr = inbuf;
    }
    static void buffer(size_t oft) {
        size_t len=fread(inbuf+oft, 1, BUF_SIZE-oft, stdin);
        inbuf[oft+len] = '\0';
    }
public:
    static void scan(double &d) {
        char *tmp;
        d = strtod(inptr, &tmp);
        if (tmp < endinbuf && tmp != inptr) {
            // successfully scanned
            inptr = tmp;
            return;
        }

        // reachs EOB before/while converting
        ptrdiff_t left=endinbuf-inptr;
        memcpy(inbuf, inptr, left);
        buffer(left);

        d = strtod(inbuf, &inptr);
    }
    static void scan(char &c) {
        c = *inptr++;
        if (c != '\0') return;

        // reaches EOB
        buffer();
        c = *inptr++;
    }
    static void scan(char *s) {
        char *pos=inptr, *src=pos;
        bool started=false;
        for (;; ++pos) {
            char tmp=*pos;
            if (tmp == '\0') {
                // unbuffers and rebuffers if reaches EOB
                ptrdiff_t count=pos-src;
                memcpy(s, src, count);
                s += count;

                buffer();
                pos = src = inbuf;
                tmp = *inbuf;
            }

            if (tmp != ' ' && tmp != '\n') {
                // not delimiters
                if (!started) {
                    started = true;
                    src = pos;
                }
            } else if (started) {
                memcpy(s, src, pos-src);
                s[pos-src] = '\0';
                inptr = ++pos;
                return;
            }

            // nops until non-delimiter char appears
        }
    }
    template <class Integral>
    static void scan(Integral &n) {
        bool started=false, neg=false;
        n = 0;
        for (;;) {
            char tmp=*inptr++;
            if (tmp == '\0') {
                buffer();
                tmp = *inptr++;
            }

            if (tmp >= '0' && tmp <= '9') {
                started = true;
                n = n*10 + tmp-'0';
            } else if (started) {
                ++tmp;
                break;
            } else if (std::is_signed<Integral>::value && tmp == '-') {
                neg = true;
            }
        }

        if (std::is_signed<Integral>::value && neg) n = -n;
    }
    template <class Arithmetic, class... Rest>
    static void scan(Arithmetic &x, Rest&... y) {
        scan(x);
        scan(y...);
    }
    static void print(double d) {
        char minibuf[20];
        size_t count=snprintf(minibuf, sizeof minibuf, "%.12f", d);
        char *tmp=outptr+count;
        if (tmp >= endoutbuf) {
            weak_flush();
            tmp = outbuf+count;
        }

        memcpy(outptr, minibuf, count);
        outptr = tmp;
    }
    static void print(char c) {
        if (outptr+1 >= endoutbuf)
            weak_flush();

        *outptr++ = c;
    }
    static void print(const char *s) {
        size_t count=strlen(s);
        char *tmp=outptr+count;
        if (tmp >= endoutbuf) {
            weak_flush();
            tmp = outbuf + count;
        }

        memcpy(outptr, s, count);
        outptr = tmp;
    }
    static void print(char *s) {
        size_t count=strlen(s);
        char *tmp=outptr+count;
        if (tmp >= endoutbuf) {
            weak_flush();
            tmp = outbuf + count;
        }

        memcpy(outptr, s, count);
        outptr = tmp;
    }
    template <size_t N>
    static void print(const char (&s)[N]) {
        size_t count=strlen(s);
        char *tmp=outptr+count;
        if (tmp >= endoutbuf) {
            weak_flush();
            tmp = outbuf + count;
        }

        memcpy(outptr, s, count);
        outptr = tmp;
    }
    template <class Integral>
    static void print(Integral n) {
        if (outptr+20 >= endoutbuf)
            weak_flush();

        if (n == 0) {
            *outptr++ = '0';
            return;
        }

        char minibuf[20], *pos=minibuf+20, *endminibuf=pos;
        if (std::is_signed<Integral>::value && n < 0) {
            *outptr++ = '-';
            n = -n;
        }

        while (n) {
            *--pos = n%10 + '0';
            n /= 10;
        }

        memcpy(outptr, pos, endminibuf-pos);
        outptr += endminibuf-pos;
    }
    template <class T, class... Rest>
    static void print(T x, Rest&&... y) {
        // prints arguments without separating characters
        print(x);
        print(y...);
    }
    template <class T>
    static void println(T x) {
        print(x, '\n');
    }
    template <class T, class... Rest>
    static void println(T x, Rest&&... y) {
        // prints arguments separated by a single space and terminates the line
        print(x, ' ');
        println(y...);
    }
    template <class T>
    static void printlns(T x) {
        print(x, '\n');
    }
    template <class T, class... Rest>
    static void printlns(T x, Rest&&... y) {
        // prints each of arguments per line
        print(x, '\n');
        printlns(y...);
    }
    static void flush() {
        // flushes the buffer
        // should be called before main() returns
        fwrite(outbuf, 1, outptr-outbuf, stdout);
        fflush(stdout);
        outptr = outbuf;
    }
};

char FastIO::inbuf[], *FastIO::inptr=FastIO::inbuf;
char *FastIO::endinbuf=inbuf+FastIO::BUF_SIZE;
char FastIO::outbuf[], *FastIO::outptr=FastIO::outbuf;
char *FastIO::endoutbuf=outbuf+FastIO::BUF_SIZE;

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 (rank(x) < rank(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;
    int Q;
    FastIO::scan(N, Q);

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

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

    FastIO::flush();
    return 0;
}

Submission Info

Submission Time
Task B - Union Find
User rsk0315
Language C++14 (GCC 5.4.1)
Score 100
Code Size 7073 Byte
Status AC
Exec Time 8 ms
Memory 1408 KB

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 4 ms 896 KB
subtask_01_02.txt AC 1 ms 640 KB
subtask_01_03.txt AC 5 ms 1280 KB
subtask_01_04.txt AC 8 ms 1408 KB
subtask_01_05.txt AC 1 ms 384 KB
subtask_01_06.txt AC 2 ms 768 KB
subtask_01_07.txt AC 7 ms 1024 KB
subtask_01_08.txt AC 8 ms 1408 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 1 ms 640 KB
subtask_01_11.txt AC 5 ms 1152 KB
subtask_01_12.txt AC 8 ms 1408 KB
subtask_01_13.txt AC 6 ms 1024 KB
subtask_01_14.txt AC 1 ms 640 KB
subtask_01_15.txt AC 5 ms 1024 KB
subtask_01_16.txt AC 8 ms 1408 KB
subtask_01_17.txt AC 8 ms 1152 KB
subtask_01_18.txt AC 8 ms 1152 KB