original article
article new

Basicly "hackers" can engineer test set that blows up your unordered map into O(N) for every hash

the worst-case time complexity of unordered_map is O(n) per operation due to hash collisions, especially if the input is crafted to cause them. That’s likely why it TLE’d, while map with guaranteed O(log n) stayed safe.

use map<int,int> for a uniform balanced BST resulting in O(logN) for insertion and retrieval of values per key ,while for an unordered_map<int,int> it uses hash fns which provides O(1) amortised but in worst cases O(N) resulting in excessive hash collisions due to weak hash implemented on it , if you wanna use Unordered_map use it with a custom hash

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // https://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
                chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

and use it like unordered_map<int,int,custom_hash>X ;