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

Автор punk_tech, 3 года назад, По-английски

I was trying to solve problem D from past tourist's contest using Hopcroft-Karp's algorithm. Here's my code

Yeah, I know that this problem has an easier greedy solution but I just want to check if it is possible to solve such a problem with a complicated algorithm at all. I've done some randomized tests for my code and they showed that on test cases where t = 1 and n = 2e5 my submission would get AC 62ms but on test cases where t = 1e4 and n = 20 my code exceeds 15 sec.

I don't know what the problem is. Time complexity of Hopcroft-Karp is O(E*sqrt(V)) which is O(t * N*sqrt(N)) in my case. I have a suggestion that it can be explained by high hidden constant of the algorithm.

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

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

Yeah, why not? Here's my in-contest submission using hopcroft.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I solved it using Dinic's algorithm, and Hopcroft Karp should perform at par, if not better. Here's my submission: 122817211

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

=putin(layer); You are using memset on an array of size 1e6 for 1e4 times. It is bound to give TLE.