Submission #36861178

---

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".
//
// The size of the "idx" array is deliberately reduced from 600005 to 300005
// and @safe is commented out (for testing what happens without runtime bounds
// checking).

//@safe:
import std.stdio, core.stdc.stdio;

int[600005] fa;

void init() {
    fa[] = -1;
}

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[300005] now;
int[300005] idx;
int[600005] past;

int main() {
    init();
    int n = readint;
    int q = readint;
    for (int i = 0; i < n; i++) {
	now[i] = i;
	past[i] = i;
	idx[i] = i;
    }
    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() @trusted {
    int val;
    scanf("%d", &val); // "scanf" is not @safe and needs a @trusted wrapper
    return val;
}

Submission Info

Judge Result