Consider this problem (https://codeforces.net/contest/984/problem/D).

Solution one (https://codeforces.net/contest/984/submission/276446617) uses two recursive functions (compute_f, and compute_max_xor) that use unordered_map for memoization. It does not pass (2000 ms TLE).

Solution two (https://codeforces.net/contest/984/submission/276446798) is the same from a logic point of view, except it uses Dynamic Programming. It passes in 546 ms.

I thought it could be because of hash collision some people have added to hack some other people but adding a random custom_hash did not help whatsoever.

Does the overhead of using an unordered_map that HIGH? Big enough to bring a x4 in time? Or am I missing something else?

Thank you!