EbraM96's blog

By EbraM96, history, 5 weeks ago, In English,

http://codeforces.com/gym/100495/problem/A

I don't know why this code produces a RTE!

Solution

Could any one please help me find the problem with it?

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps the program has accessed a non-existent element of the array, dividing by zero, and so on. Perhaps the C++ program does not end with the "return 0" operator or otherwise returns a non-zero return code.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know these things and I can not find any in my program.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe it's because you are assigning unsigned long long -1 to dist[i] which is type signed long long. Thus you will get the value -1 instead of the intended infinity. Since the State struct holds a signed long long, w>dist[u] will always be true.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I changed it to 1e12 and still RTE.

    And by the way, unsigned long long(-1) will produce the maximum value in unsigned long long.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm sorry I was not able to help D: It might have to do with the bitwise logic from lines 78 — 83. Are you sure they cannot go out of bounds?

      Also, have you tried min/max edge cases? Maybe you can use SPOJ toolkit to generate test cases, and also print out debugging output to help check.

      I know I am stating the obvious but this is the best I can offer. Good luck!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the mask will contain 12 bits at max so the array should be sized as (1<<12) and that should suffice.

        I even resized it to (1<<12)*10 and still rte.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Does the problem allow cycles/self loops? If it does, maybe you could store every visited start node in a lookup array and if already visited don't visit. But I do not think that will be the error for rte. Also, will there ever be negative edges?

          Another thing is, do you need to reset some data for each test case?

          I hope this helps.