# Map with vector as a key in C++

I am currently solving this problem, and I get TLE on three test cases due to the slow nature of maps with vectors as keys.

Does anyone know why it’s slow?

``````#include <bits/stdc++.h>

using namespace std;
using ll = int;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;

#define forn(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rofn(i, n) for(ll i = n; i >= 0; i--)
#define ROF(i, a, b) for(ll i = a; i >= b; i--)
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))

int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
long long n; cin >> n;
map<vl, ll> mp;
long long ans = 0;
forn(i, n){
vl flavors(5);
forn(i, 5) cin >> flavors[i];
sor(flavors);
forn(j, 32){
vl cur;
forn(k, 5){
if(j & (1 << k)){
cur.pb(flavors[k]);
}
}
if(cur.size() & 1){
ans += mp[cur];
} else {
ans -= mp[cur];
}
if(cur.size()) mp[cur]++;
}
}
cout << (n * (n - 1) / 2) - ans << endl;
}
``````

I even tried converting from `long long` to `int`

It’s generally the case that operations on vectors with size bounded above by a constant will be a little slower than the corresponding operations on fixed-size arrays.

Looks like the time limit was set so tight that the analysis solution doesn’t even pass Same with the only user-submitted solution on USACO Guide … (USACO Monthlies)

To pass comfortably below the time limit you’ll probably need to do at least one of the following:

1. Replace the map in the analysis solution with a sorted vector.
2. Use some sort of hashing (ex. XOR Hashing [TUTORIAL] - Codeforces).

Some solutions that work:

Solution 1
``````#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class X, class Y>
bool minimize(X &x, const Y &y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
} else return false;
}

const int N = 5e4 + 7, M = 1e6 + 7, oo = 1e9 + 7, MOD = 1e9 + 7;

int n, a[6], cnt[6];

signed main() {
fastIO;
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
cin >> n; vector<int> x; x.reserve(5);
vector<vector<int>> dp;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 5; j++)
cin >> a[j];
sort(a, a + 5);
for (int m = 1; m < (1 << 5); m++) {
x.clear();
for (int j = 0; j < 5; j++)
if (getBit(m, j)) x.pb(a[j]);
dp.push_back(x);
}
}
sort(begin(dp), end(dp));

ll ans = 1ll * n * (n - 1) / 2;
for (int i = 0; i < size(dp); ) {
int j = i;
while (i < size(dp) && dp.at(i) == dp.at(j)) ++i;
int dif = i-j;
if (sz(dp.at(j))&1) ans -= 1ll*dif*(dif-1)/2;
else ans += 1ll*dif*(dif-1)/2;
}
cout << ans;
}
``````
Solution 2
``````#include <bits/stdc++.h>

using namespace std;
using ll = int;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;

#define forn(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rofn(i, n) for(ll i = n; i >= 0; i--)
#define ROF(i, a, b) for(ll i = a; i >= b; i--)
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))

int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
mt19937_64 rng;
long long n; cin >> n;
vector<uint64_t> hashes(1000001);
for (int i = 1; i <= 1000000; ++i) hashes[i] = rng();
unordered_map<uint64_t, ll> mp;
long long ans = 0;
forn(i, n){
vl flavors(5);
forn(i, 5) cin >> flavors[i];
sor(flavors);
forn(j, 32){
uint64_t cur = 0;
int cnt = 0;
forn(k, 5){
if(j & (1 << k)){
cur ^= hashes[flavors[k]];
++cnt;
}
}
if(cnt & 1){
ans += mp[cur];
} else {
ans -= mp[cur];
}
if(cnt) mp[cur]++;
}
}
cout << (n * (n - 1) / 2) - ans << endl;
}
``````
1 Like