satyaki3794's blog

Getting TLE on "Shaass the Great", 178-DIV2-E
By satyaki3794, 9 years ago, In English

I recently tried the problem 294E - Shaass the Great and my submission is 10704270.

I am getting TLE on test 8 which is a maxtest (5000 nodes). I am unable to figure out my mistake. Could someone please take a look at it and guide me in the right direction, if they can figure out what my mistake is?

My logic is as follows: I used a n^2 algorithm. One by one, I selected each edge as the one I will delete and found the optimal vertices in the two trees created (optimal means has the least sum of distances to other vertices in the same tree). Then I join those two to get the answer and compare it with the global answer.

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

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think that this is a correct solution. I've got the same problem. When I looked at accepted solutions they were running for > 2s. And the problem is that the package was not updated, so they took the execution time of your program and simply multiply it by 2. There is a good chance that your solution runs > 2s and that's why it is judged as TLE (after multiplication), because time limit is 4 s for this problem.

Edit: For my case changing from MS VS to Gnu C++ 11 solved the issue, but it looks like you are already using GNU C++ 11, so maybe you would like to try a different version of GNU C++?

→ Reply