#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
int n;
vector<pair<string,string> > eg;
int G[MAX];
vector<int> cptG[MAX];
int dp[MAX][2];
void dfs(int v,int p,vector<bool>& vis,vector<bool>& tmpvis,vector<int>& ccl,int& stt) {
tmpvis[v]=true;
for (int i:cptG[v]) {
if (tmpvis[i]) {
stt=i;
ccl.push_back(v);
if (i==v) stt=0;
return;
}
if (i==p) continue;
dfs(i,v,vis,tmpvis,ccl,stt);
if (stt>=0) {
if (stt>0) {
ccl.push_back(v);
if (stt==v) stt=0;
}
return;
}
}
tmpvis[v]=false;
}
void dfsvis(int v,vector<bool>& vis) {
vis[v]=true;
for (int i:cptG[v]) {
if (vis[i]) continue;
dfsvis(i,vis);
}
}
void dfs2(int v,int p,vector<bool>& isccl) {
if (cptG[v].size()==1) {
dp[v][0]=0;
dp[v][1]=-INF;
return;
}
dp[v][0]=0;
for (int i:cptG[v]) {
if (i==p) continue;
if (isccl[i]) continue;
dfs2(i,v,isccl);
dp[v][0]+=max(dp[i][0],dp[i][1]);
}
dp[v][1]=0;
for (int i:cptG[v]) {
if (i==p) continue;
if (isccl[i]) continue;
dp[v][1]=max(dp[v][1],dp[v][0]-max(dp[i][0],dp[i][1])+dp[i][0]+1);
}
}
int main() {
speed;
cin>>n;
vector<string> dct;
for (int i=0;i<n;i++) {
string a,b;
cin>>a>>b;
eg.emplace_back(a,b);
dct.push_back(a);
dct.push_back(b);
}
sort(all(dct));
dct.resize(unique(all(dct))-dct.begin());
// for (string s:dct) cout<<s<<"\n";
// cout<<"name\n";
fill(G,G+n,n);
for (int i=0;i<n;i++) {
auto [a,b]=eg[i];
int va=lower_bound(all(dct),a)-dct.begin();
int vb=lower_bound(all(dct),b)-dct.begin();
G[va]=vb;
if (va!=G[G[va]]) cptG[va].push_back(vb);
if (va!=vb and va!=G[G[va]]) cptG[vb].push_back(va);
}
// for (int i=0;i<n;i++) {
// cout<<i<<" : ";
// for (int j:cptG[i]) cout<<j<<" ";
// cout<<"\n";
// }
if (n&1) {
cout<<"-1\n";
return 0;
}
vector<bool> vis(n,0),tmpvis(n,0);
vector<bool> isccl(n,0);
int ttl=0;
for (int i=0;i<n;i++) {
if (vis[i]) continue;
vector<int> ccl;
int stt=-1;
dfs(i,-1,vis,tmpvis,ccl,stt);
dfsvis(i,vis);
// cout<<i<<" i\n"<<flush;
// for (int j:ccl) cout<<j<<" ";
// cout<<" ccl\n"<<flush;
for (int j:ccl) isccl[j]=true;
for (int j:ccl) {
// cout<<j<<" rt\n"<<flush;
dfs2(j,-1,isccl);
}
vector<vector<int> > cdp(ccl.size(),vector<int>(2,0));
cdp[0][0]=dp[ccl[0]][0];
cdp[0][1]=dp[ccl[0]][1];
for (i=1;i<ccl.size();i++) {
cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
}
int ans=max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]);
int tmp=ccl[0];
for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
ccl[ccl.size()-1]=tmp;
fill(all(cdp),vector<int>(2,0));
cdp[0][0]=dp[ccl[0]][0];
cdp[0][1]=dp[ccl[0]][1];
for (i=1;i<ccl.size();i++) {
cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
}
ans=max(ans,max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]));
ttl+=ans;
}
cout<<n-ttl<<"\n";
return 0;
}
Compilation message
polygon.cpp: In function 'int main()':
polygon.cpp:127:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (i=1;i<ccl.size();i++) {
| ~^~~~~~~~~~~
polygon.cpp:133:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
| ~^~~~~~~~~~~~~
polygon.cpp:138:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (i=1;i<ccl.size();i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 4 |
Runtime error |
814 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
6492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
42376 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 4 |
Runtime error |
814 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
