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.
Yeah, why not? Here's my in-contest submission using hopcroft.
I solved it using Dinic's algorithm, and Hopcroft Karp should perform at par, if not better. Here's my submission: 122817211
=
putin(layer);You are using memset on an array of size 1e6 for 1e4 times. It is bound to give TLE.Thank you a lot! I was really lost before.