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:

Previous

Modified

Am I overthinking, or is there some explanation to this?