Блог пользователя WhaleVomit

Changing bounds makes WA solution AC for unknown reason
Автор WhaleVomit, история, 6 лет назад, По-английски

I was working on the problem Xenia and Tree here: http://codeforces.com/problemset/problem/342/E

But the problem statement doesn't actually matter.

My first solution gets WA: http://codeforces.com/contest/342/submission/33140735

and my second gets AC: http://codeforces.com/contest/342/submission/33140905

The only difference between the two submissions that mattered is that I increased MAX_N from 100000 to 100005. This should not have changed anything, because I'm pretty sure my array sizes were all large enough. So why did this happen?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For your WA submission on test #4 the input set has n = 105. So when your code tries to access the 105 th node it should get RTE because the last node you can access is 9999. But sometimes it access the next value in the memory after 9999 th index and this gives a WA. This behavior is undefined.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This gets AC: http://codeforces.com/contest/342/submission/33200103. The change is line 99:

M00(i, numNodes) child[par[i]].PB(i);

becomes

M00(i, numNodes) if (par[i] != -1) child[par[i]].PB(i);

(I just launched valgrind on the input example with MAX_N = 5! ;))

→ Ответить