fofao_funk's blog

By fofao_funk, history, 8 years ago, In English

Hi.

I solved problem 519E - A and B and Lecture Rooms using the solution suggested by the editorial and still it is slow when compared to others solutions. The strange thing is that there are some cases with maximum N and M that take ~0.1s to run, but there are others that are way slower, even though N and M are not maximum.

My solution took ~1.6s while there are some that took ~0.1s.

Why is my solution so slow?

My solution: 16864045 Example of a fast one: 10141947

Thanks for the help.

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

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

The first two things I saw:

  • the way you store the graph (std::vector is not the fastest solution)
  • the way you construct the ancestors' matrix (not cache-friendly)

There may be more...