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 :( 
It is UB, which may manifest itself as WA, RE, TLE, AC or anything else ("Compilers are not required to diagnose undefined behavior (although many simple situations are diagnosed), and the compiled program is not required to do anything meaningful").
Thanks. Hope AtCoder can diagnose it :(
Otherwise, it will waste me (and some other competitive programmer) a lot of time.
Codeforces too (no input.txt/output.txt, verdict: MLE on test 1)
This is not an issue for codeforces or atcoder to fix. This is just how c++ works.
If you want error messages to show up correctly and aren't going to understand how the underlying language works (and it is very complicated) it might be best to use an interpreted language instead of a compiled language.
Adding command line option
-fsanitize=address,undefinedfor GCC when compiling C++ code can make it detect out of bounds array accesses and other bugs at runtime. But this is not free and makes the program slower, which means a higher risk of TLE. I tried to check if it's possible to override these command line options from the source code via some pragma. But#pragma GCC optimizeseems to reject the sanitizer options and I couldn't find any other similar pragma.If this is really bothering you and causing troubles during contests, then you can try some other safer programming language instead of C++:
Check this blog
For example, your C++ solution (87 ms) can be directly converted to D (96 ms). But it's still unsafe and adding
@safe:line at the top of the source file is necessary for the compiler to start rejecting suspicious stuff and do runtime checks. After this is done, the compiler complains about scanf/printf:The compilation errors can be resolved by making a small wrapper function
readint()for scanf with@trustedattribute, which tells the compiler that it's alright to relax safety in this particular function. Now the following D code is safe (113 ms). Let's reduce the "idx" array size from 600005 down to 300005 to see what happens:RE if the code is annotated as @safe. Runtime bounds checks can catch this bug.
WA if the code is not annotated as @safe. Out of bounds accesses just corrupt memory or read invalid values (similar to C++).
It's also possible to get rid of global arrays, dynamically allocate as much memory as needed and use faster I/O: https://atcoder.jp/contests/abc279/submissions/36861631 (71 ms). Your original C++ solution can be optimized for better performance too.
The peak performance of Rust or D code is expected to be roughly the same as C++ if all compilers use the same code generation backend (GCC or LLVM) and opt out of safety in the performance critical parts.
Do you mean https://codeforces.me/problemset/customtest ? Which compiler have you selected? When running your code with no input, "Clang++20 Diagnostics" says: