osama's blog

By osama, history, 9 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
9 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

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.

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

    Thanks, I really appreciate your help.