/// I'm only brave when I have to be
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;
template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;
constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 1e5, SQ = 300, INF = 2e18 + 8, LGN = 21, mod = 998244353, P = 131113;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool mark[N], used[N];
int n, pt, sz, ans, mat[25][25], dp[(1<<LGN)];
map <string, int> m;
vector <int> adj[N];
void dfs (int u){
mark[u] = true;
++ sz;
for (int i : adj[u]){
if (!mark[i]){
dfs (i);
}
}
return;
}
void dfs2 (int u, int par = -1){
mark[u] = true;
for (int i : adj[u]){
if (!mark[i]){
dfs2 (i, u);
}
}
if (par != -1 && !used[u] && !used[par]){
++ ans;
used[u] = true;
used[par] = true;
}
return;
}
int32_t main(){
fast_io;
cin >> n;
if (n & 1){
cout << -1;
return 0;
}
if (n <= 20){
set <string> s;
FOR (i, 0, n){
string ss, tt;
cin >> ss >> tt;
if (s.find(ss) == s.end()){
m[ss] = pt ++;
s.insert(ss);
}
if (s.find(tt) == s.end()){
m[tt] = pt ++;
s.insert(tt);
}
mat[m[ss]][m[tt]] = 1;
//cout << m[ss] << " " << m[tt] << '\n';
}
fill (dp, dp + (1 << LGN), INF);
dp[0] = 0;
for (int i = 1; i < (1 << n); ++ i){
for (int j = 0; j < n; ++ j){
if (i & (1 << j)){
for (int k = 0; k < n; ++ k){
if ((i & (1 << k)) && j != k){
dp[i] = min (dp[i], dp[i^(1<<j)^(1<<k)] + 2 - mat[j][k] - mat[k][j]);
//cout << i << " updated from " << (i^(1<<j)^(1<<k)) << " " << dp[i^(1<<j)^(1<<k)] << " " << j << " " << k << " : " << mat[j][k] << " " << mat[k][j] << '\n';
}
}
}
}
//cout << i << " " << dp[i] << '\n';
}
cout << dp[(1<<n)-1];
return 0;
}
set <string> s;
FOR (i, 0, n){
string ss, tt;
cin >> ss >> tt;
s.insert(tt);
if (m[ss] == 0){
m[ss] = ++ pt;
}
if (m[tt] == 0){
m[tt] = ++ pt;
}
adj[m[ss]].pb(m[tt]);
}
if (s.size() == pt){
for (int i = 1; i <= n; ++ i){
if (!mark[i]){
dfs (i);
if (sz == 2){
sz = 0;
continue;
}
ans += (sz + 1) / 2;
sz = 0;
}
}
cout << ans;
}
else {
FOR (i, 1, pt + 1){
if (!mark[i]){
dfs2 (i);
}
}
cout << n - ans << '\n';
}
return 0;
}
// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present
Compilation message
polygon.cpp: In function 'int32_t main()':
polygon.cpp:125:16: warning: comparison of integer expressions of different signedness: 'std::set<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
125 | if (s.size() == pt){
| ~~~~~~~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
694 ms |
21560 KB |
Output is correct |
2 |
Correct |
687 ms |
21556 KB |
Output is correct |
3 |
Correct |
708 ms |
21340 KB |
Output is correct |
4 |
Correct |
4 ms |
21336 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
1 ms |
6744 KB |
Output is correct |
7 |
Correct |
704 ms |
21340 KB |
Output is correct |
8 |
Correct |
695 ms |
21560 KB |
Output is correct |
9 |
Correct |
701 ms |
21560 KB |
Output is correct |
10 |
Correct |
703 ms |
21592 KB |
Output is correct |
11 |
Correct |
701 ms |
21588 KB |
Output is correct |
12 |
Correct |
4 ms |
21336 KB |
Output is correct |
13 |
Correct |
4 ms |
21340 KB |
Output is correct |
14 |
Correct |
5 ms |
21340 KB |
Output is correct |
15 |
Correct |
4 ms |
21340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
21340 KB |
Output is correct |
2 |
Correct |
4 ms |
21588 KB |
Output is correct |
3 |
Correct |
4 ms |
21336 KB |
Output is correct |
4 |
Correct |
242 ms |
28160 KB |
Output is correct |
5 |
Correct |
261 ms |
25572 KB |
Output is correct |
6 |
Correct |
236 ms |
28884 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
243 ms |
23812 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
694 ms |
21560 KB |
Output is correct |
2 |
Correct |
687 ms |
21556 KB |
Output is correct |
3 |
Correct |
708 ms |
21340 KB |
Output is correct |
4 |
Correct |
4 ms |
21336 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
1 ms |
6744 KB |
Output is correct |
7 |
Correct |
704 ms |
21340 KB |
Output is correct |
8 |
Correct |
695 ms |
21560 KB |
Output is correct |
9 |
Correct |
701 ms |
21560 KB |
Output is correct |
10 |
Correct |
703 ms |
21592 KB |
Output is correct |
11 |
Correct |
701 ms |
21588 KB |
Output is correct |
12 |
Correct |
4 ms |
21336 KB |
Output is correct |
13 |
Correct |
4 ms |
21340 KB |
Output is correct |
14 |
Correct |
5 ms |
21340 KB |
Output is correct |
15 |
Correct |
4 ms |
21340 KB |
Output is correct |
16 |
Correct |
4 ms |
21340 KB |
Output is correct |
17 |
Correct |
4 ms |
21588 KB |
Output is correct |
18 |
Correct |
4 ms |
21336 KB |
Output is correct |
19 |
Correct |
242 ms |
28160 KB |
Output is correct |
20 |
Correct |
261 ms |
25572 KB |
Output is correct |
21 |
Correct |
236 ms |
28884 KB |
Output is correct |
22 |
Correct |
1 ms |
6748 KB |
Output is correct |
23 |
Incorrect |
243 ms |
23812 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |