//Bismi Allah
#include "bits/stdc++.h"
using namespace std;
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
map <string,int> mp;
vector <int> love(n, 0);
/*vector <int> used(n, 0), dp(n, 0), g[n], unite(n, 0), loved(n, 0), rk(n, 0);
function <void(int,int)> dfs=[&](int v, int p) {
used[v] = 1;
rk[v] = 1;
for(auto u : g[v]) {
if(used[u]) continue;
dfs(u, v);
rk[v] += rk[u];
}
if(unite[v]) return;
if(p != -1 && unite[p] == 0) {
unite[p] = 1;
unite[v] = 1;
}
};*/
for(int i = 0; i < n; i ++) {
string u, v;
cin >> u >> v;
if(mp.count(u) == 0) mp[u] = mp.size();
if(mp.count(v) == 0) mp[v] = mp.size();
love[mp[u]] = mp[v];
}
if(n <= 20) {
vector <int> forMask;
for(int mask = 0; mask < (1 << n); mask ++) {
if(__builtin_popcount(mask) % 2 != 0) continue;
forMask.push_back(mask);
}
sort(forMask.begin(), forMask.end(), [](int a, int b) {
return __builtin_popcount(a) < __builtin_popcount(b);
});
vector <int> dp(1 << n, 1e9);
dp[0] = 0;
for(auto mask : forMask) {
if(mask == 0) continue;
vector <int> v;
for(int i = 0; i < n; i ++) {
if(mask & (1 << i)) {
v.push_back(i);
}
}
for(int i = 0; i < v.size(); i ++) {
for(int j = i + 1; j < v.size(); j ++) {
int cost = 0, newmask = mask;
newmask ^= (1 << v[i]);
newmask ^= (1 << v[j]);
if(love[v[i]] == v[j] && love[v[j]] == v[i]) cost = 0;
else if(love[v[i]] == v[j] || love[v[j]] == v[i]) cost = 1;
else cost = 2;
dp[mask] = min(dp[mask], dp[newmask] + cost);
}
}
}
cout << dp[(1 << n) - 1];
return 0;
}
/*if(*min_element(loved.begin(), loved.end()) >= 1) {
if(n % 2 == 1) {
// assert(false);
cout << -1;
return 0;
}
int ans = 0, mod = 0;
for(int i = 0; i < n; i ++) {
if(used[i]) continue;
dfs(i, -1);
if(rk[i] == 2) continue;
ans += rk[i] / 2;
mod += (rk[i] % 2);
}
if(mod % 2 == 1) cout << -1;
else cout << ans + mod;
return 0;
}
if(n % 2 == 1) {
// assert(false);
cout << -1;
return 0;
}
int ans = 0, mod = 0;
for(int i = 0; i < n; i ++) {
if(used[i]) continue;
dfs(i, -1);
}
for(auto i : unite) {
ans += (i == 1);
mod += (i == 0);
}
cout << ans/2+mod;*/
return 0;
}
Compilation message
polygon.cpp: In function 'int main()':
polygon.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
polygon.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int j = i + 1; j < v.size(); j ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
6600 KB |
Output is correct |
| 2 |
Correct |
193 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
219 ms |
6736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
135 ms |
8656 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
8652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
6600 KB |
Output is correct |
| 2 |
Correct |
193 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
219 ms |
6736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
