Блог пользователя fofao_funk

Автор fofao_funk, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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