M.A.H.M.O.O.D's blog

Need help in an old IOI problem "IOI '94 the clocks"
By M.A.H.M.O.O.D, history, 8 years ago, In English

Good day everybody.

So yesterday I was trying to solve this problem here and now I need some help please.

So my problem is this in my soultion I got AC on the first test and RE on the rest I looked in the help section of the site and it turned out the RE might be caused by some large STL the only STL I was using was a queue so I put an if statment that if the queue size was bigger that 10000 stop putting stuff in the queue and it worked...sort of.

You see now I'm getting WA on tests 2 , 3 and 4 and AC on the rest and on tests 2 , 3 and 4 my program isn't outputing anything and that's because of the queue limit so now I'm asking you this can you tell me what is wrong with my code and how to fix it or do you have a working code for the problem or is there any site that has working C++ codes for old IOI problems.

Here's my code.

Any help is much appreciated.

thank you and sorry for the long post.

:)

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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Unfortunately it doesn't seem like you are caching.

Normally in a BFS you would maintain a "seen" array to make sure you don't come back to the same vertex multiple times. I don't see this in your implementation.

Please correct me if I am wrong.

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

    I tried putting a map of < pair < vector < short > , vector < short > > , bool > but the problem that was caused by the queue will now be caused by the map because its size will be huge too.

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

      The fact that you say that suggests you haven't solved the problem yet.

      I suggest you return and evaluate the complexity properly again by finding some more observations. I advise you not to read the spoiler until you have tried to solve the problem yourself.

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

        Yeah, but I bet that because the problem is from 1994, the intended solution has smaller complexity

        Spoiler
        → Reply