fofao_funk's blog

By fofao_funk, history, 9 years ago, In English

Hi.

I solved problem 519E - A и B и аудитории 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

»
9 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...