#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
int n;
vector<string> a, b;
vector<string> compr;
map<string,int> compress;
vector<int> g[N+10];
int used[N + 10];
vector<int> G[N+10];
int idx[N+10];
vector<int> topo;
int num=1;
vector<int> sub[N+10];
void dfs(int v){
used[v] = 1;
for(int to : g[v]){
if(!used[to]){
dfs(to);
}
}
topo.push_back(v);
}
void dfs2(int v){
used[v] = 1;
idx[v] = num;
sub[num].push_back(v);
for(int to : G[v]){
if(!used[to]){
dfs2(to);
}
}
}
int ans;
vector<int> cond[N+10];
int taken[N + 10];
void dfs3(int v, int par){
used[v] = 1;
for(int to : cond[v]){
if(used[to]) continue;
dfs3(to, v);
}
if(par != -1 && !taken[par] && !taken[v]){
cout << v << " " << par << '\n';
taken[v] = taken[par] = 1;
ans++;
}
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
a.resize(n);
b.resize(n);
for(int i = 0;i < n; i++){
cin >> a[i] >> b[i];
compr.push_back(a[i]);
}
sort(all(compr));
int cnt1 = 1;
for(auto x : compr){
compress[x] = cnt1++;
}
// for(int i = 0;i < n; i++){
// cout << a[i] << " = " << compress[a[i]] << '\n';
// }
for(int i = 0;i < n; i++){
g[compress[a[i]]].push_back(compress[b[i]]);
G[compress[b[i]]].push_back(compress[a[i]]);
}
if(n%2 == 1){
cout << "-1";
return 0;
}
// if(n <= 20){
// vector<int> dp((1<<n), INT_MAX);
// dp[0] = 0;
// for(int mask = 0; mask < (1<<n); mask++){
// for(int i = 0;i < n; i++){
// for(int j = i + 1; j < n; j++){
// int new_mask = mask | (1<<i);
// new_mask|= (1<<j);
// int c = (g[i+1][0] != j + 1) + (g[j + 1][0] != (i + 1));
// dp[new_mask] = min(dp[new_mask], dp[mask] + c);
// }
// }
// }
// cout << dp[(1<<n)-1];
// return 0;
// }
for(int i = 1;i <= n; i++){
if(!used[i]){
dfs(i);
}
}
reverse(all(topo));
for(int i = 1;i <= n; i++) used[i] = 0;
for(int i : topo){
if(!used[i]){
dfs2(i);
num++;
}
}
for(int i = 1;i <= n; i++){
int cnt = sub[i].size();
if(cnt > 2){
ans+= (cnt / 2);
}
if(cnt % 2 == 0){
taken[i] = 1;
}
}
for(int i = 1;i <= n; i++){
set<int> st;
for(int to : g[i]){
if(idx[i] != idx[to]){
st.insert(idx[to]);
}
}
for(int u : st){
cond[idx[i]].push_back(u);
cond[u].push_back(idx[i]);
}
}
// for(int i = 1;i < num; i++){
// cout << i << " = ";
// for(int x : sub[i]){
// cout << x << ' ';
// }
// cout << '\n';
// }
for(int i = 1;i <= n; i++){
used[i] = 0;
}
for(int i = 1;i < num; i++){
if(!used[i]){
dfs3(i, -1);
}
}
for(int i = 1;i < num; i++){
if(taken[i] != 1) ans++;
}
cout << ans;
return 0;
}
Compilation message
polygon.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
63 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11868 KB |
Output is correct |
| 3 |
Correct |
2 ms |
11868 KB |
Output is correct |
| 4 |
Correct |
222 ms |
42836 KB |
Output is correct |
| 5 |
Correct |
203 ms |
37712 KB |
Output is correct |
| 6 |
Correct |
219 ms |
42928 KB |
Output is correct |
| 7 |
Correct |
194 ms |
36420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
43700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
