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

Автор osama, история, 9 лет назад, По-английски

Recently I've tried to solve this problem 160D - Edges in MST but there was a bug in my code, I've tried to debug the code but that was just wasting time, then I've rewritten the code again and got AC :D. Making a comparison between the two codes was so weird they were almost identical, I read about undefined - behavior in C++ but I couldn't find anything like that.

WA code: 12013993

AC code: 12013990

Any help would be appreciated.

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

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

It seems like you have an index out of bounds somewhere in your code. I changed MAXN constant and it passed(12110970).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    You are right but shouldn't it gives RTE. and why did it passed in the second submission?

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

You actually do have undefined behavior possible in both of your programs. Array s should be 2N size as you store two elements for each edge. What actually happened is that array dfs_num is allocated right after array s in memory so you would use it as part of s you are missing and overwrite its data, in second program s is after all other arrays so you would mess with memory that you don't know anything about and get lucky.