So this is my code to ABC279F:
#include <bits/stdc++.h>
using namespace std;
int fa[600005];
void init() {
memset(fa, -1, sizeof fa);
}
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 now[300005], idx[300005], past[600005];
int main() {
init();
int n, q;
scanf("%d %d", &n, &q);
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;
scanf("%d", &tp);
if (tp == 1) {
int x, y;
scanf("%d %d", &x, &y);
x--, y--;
unite(now[y], now[x]);
now[y] = ++cntn;
past[cntn] = y;
} else if (tp == 2) {
int x;
scanf("%d", &x);
x--;
idx[++cnt] = now[x];
} else {
int x;
scanf("%d", &x);
x--;
printf("%d\n", past[find_root(idx[x])] + 1);
}
// for (int i = 0; i < n; i++) {
// cerr << now[i] << " ";
// }
// cerr << endl;
}
return 0;
}
It should be RE (Though the size of "idx" is 300005), but it judged as WA.
Why?
And it wasted me a lot of time :(