harvey_wzy's blog

It should be RE, but it was judged as WA......
By harvey_wzy, history, 2 years ago, In English

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 :(

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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").

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +34 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Adding command line option -fsanitize=address,undefined for 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 optimize seems 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++:

      Rust is a relatively popular choice
      D language is another possible alternative

      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.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Codeforces too (no input.txt/output.txt, verdict: MLE on test 1)

      Do you mean https://codeforces.me/problemset/customtest ? Which compiler have you selected? When running your code with no input, "Clang++20 Diagnostics" says:

      Spoiler
      → Reply