I know the difference is not huge, but I was consistently getting similar results, so I thought of asking it.
I recently learned Kuhn's algorithm, and was solving this problem. (I know it's slow, so the TLE makes sense)
When I realised that we only need the edge from the bipartite part we're starting from, I modified the code accordingly:
- Changed the adjacency list size from $$$l + r$$$ to $$$l$$$.
- Only have edge from $$$a_i \rightarrow b_i$$$ and not in the other direction.
I was not expecting a huge time save, but to my surprise, the new code took more time in almost every big test case (one of the test case taking 600ms more time).
Submissions:
Am I overthinking, or is there some explanation to this?
