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

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

Solution two (https://mirror.codeforces.com/contest/984/submission/276446798) is the same from a logic point of view (dp corresponds to compute_f and dp_max corresponds to compute_max_xor), except it uses Dynamic Programming. It passes in 546 ms.

I thought it could be tjat different because of hash collisions. Some people hack some other people by using clever inputs that blow up hashmaps ... 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!