Submission #36861631

---

Source Code Expand

// Not my code! Taken from https://atcoder.jp/contests/abc279/submissions/36844595
// and directly line by line converted to D language. Added "@safe:" directive
// at the top, moved "scanf" into a small @trusted wrapper function and replaced
// "printf" with "writeln". Replaced "scanf" with faster I/O code and removed
// global arrays. Arrays are dynamically allocated.

@safe:
import std.stdio, std.range, std.algorithm;

int main() {
    int n = readint;
    int q = readint;

    auto now = iota(n).array;
    auto past = iota(n + q).array;
    auto idx = iota(n + q).array;
    auto fa = [-1].replicate(n + q);

    int find_root(int x) {
        if (fa[x] == -1) {
            return x;
        }
        return fa[x] = find_root(fa[x]);
    }

    void unite(int x, int y) {
        if (find_root(x) != find_root(y) && find_root(x) != -1) {
            fa[find_root(x)] = find_root(y);
        }
    }

    int cntn = n - 1;
    int cnt = n - 1;
    while (q--) {
	int tp = readint;
	if (tp == 1) {
	    int x = readint;
	    int y = readint;
	    x--, y--;
	    unite(now[y], now[x]);
	    now[y] = ++cntn;
	    past[cntn] = y;
	} else if (tp == 2) {
	    int x = readint;
	    x--;
	    idx[++cnt] = now[x];
	} else {
	    int x = readint;
	    x--;
	    writeln(past[find_root(idx[x])] + 1);
	}
    }
    return 0;
}

int readint() {
    return fastio.readnum!int; // we can do it even faster than "scanf"
}

// Fast I/O

import std.stdio, std.array, std.ascii, std.exception;

struct fastio {
    shared static byte[64 * 1024] buf;
    shared static byte[] avail;

    static void fillbuf() @trusted {
        if (avail.empty)
            avail = cast(shared(byte[]))stdin.rawRead(cast(byte[])buf);
        enforce(!avail.empty, "EOF");
    }

    static bool fillbuf_nothrow() @trusted {
        if (avail.empty)
            avail = cast(shared(byte[]))stdin.rawRead(cast(byte[])buf);
        return !avail.empty;
    }

    static T readnum(T)() {
        bool negative = false;
        T ans = 0;
        fillbuf();
        while (std.ascii.isWhite(avail.front)) {
            avail = avail[1 .. $];
            fillbuf();
        }
        if (avail.front == '-') {
            negative = true;
            avail = avail[1 .. $];
            fillbuf();
        }
        enforce(avail.front >= '0' && avail.front <= '9', "bad format");
        while (avail.front >= '0' && avail.front <= '9') {
            ans = ans * 10 + (avail.front - '0');
            avail = avail[1 .. $];
            if (!fillbuf_nothrow())
                break;
        }
        return negative ? -ans : ans;
    }
}

Submission Info

Judge Result