#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
map<string, int> id;
set<pair<int, int>> edges;
vector<int> gr[N];
int mchtree[N][2];
bool viz[N];
void dfsdown(int nod,int dad1,int dad2){
viz[nod] = true;
int maxdif = INT_MIN;
for(int x:gr[nod]){
if(x!=dad1 && x!=dad2 && x!= nod){
dfsdown(x, nod, 0);
mchtree[nod][0] += max(mchtree[x][0], mchtree[x][1]);
maxdif = max(maxdif, mchtree[x][0] + 1 - max(mchtree[x][0], mchtree[x][1]));
}
}
if(maxdif != INT_MIN)
mchtree[nod][1] = mchtree[nod][0] + maxdif;
}
stack<int> activ;
int dfs_cycle(int nod, int prev){
activ.push(nod);
viz[nod] = true;
for(auto x:gr[nod]){
if(viz[x] == false){
int val = dfs_cycle(x, nod);
if(val != -1)
return val;
}
else if(x!= prev && viz[x] == true){
return x;
}
}
activ.pop();
return -1;
}
int mch[N][2];
int makedp(vector<int> &cycle, int l,int r){
if(l > r)
return 0;
mch[l][0] = mchtree[cycle[l]][0], mch[l][1] = mchtree[cycle[l]][1];
for(int i=l + 1; i<=r;i++){
int nod = cycle[i];
mch[i][1] = max(mchtree[nod][1] + max(mch[i-1][0], mch[i-1][1]), mchtree[nod][0] + 1 + mch[i-1][0]);
mch[i][0] = max(mch[i-1][0], mch[i-1][1]) + mchtree[nod][0];
}
return max(mch[r][0], mch[r][1]);
}
int solve_cycle(vector<int> &cycle){
int csize = cycle.size();
for(int i=0;i<cycle.size();i++){
int next = cycle[(i + 1)%csize], prev = cycle[(i - 1 + csize)%csize];
dfsdown(cycle[i], next, prev);
}
int answer = 0;
// pot lua 0 - csize -1; 0 -1; 0 blocat din copac sau gol
int ansc = 1 + mchtree[cycle[0]][0] + mchtree[cycle[csize - 1]][0] + makedp(cycle, 1, csize - 2);
answer = max(answer, ansc);
ansc = 1 + mchtree[cycle[0]][0] + mchtree[cycle[1]][0] + makedp(cycle, 2, csize - 1);
answer = max(answer, ansc);
ansc = max(mchtree[cycle[0]][0], mchtree[cycle[0]][1]) + makedp(cycle, 1, csize - 1);
answer = max(answer, ansc);
return answer;
}
int main()
{
freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n = 0;
int m;
cin>>m;
for(int i=1;i<=m;i++){
string s;
int x, y;
cin>>s;
if(!id.count(s))
id[s] = ++n;
x = id[s];
cin>>s;
if(!id.count(s))
id[s] = ++n;
y = id[s];
if(x > y)
swap(x, y);
if(edges.count({x, y}))
continue;
if(x != y){
gr[x].push_back(y);
gr[y].push_back(x);
}
edges.insert({x, y});
}
if(n%2 == 1){
cout<<"-1";
return 0;
}
int answer = 0;
for(int i=1;i<=n;i++){
if(viz[i] == false){
activ = stack<int>();
int valcyc = dfs_cycle(i, 0);
if(valcyc == -1){
dfsdown(i, 0, 0);
answer+= max(mchtree[i][0], mchtree[i][1]);
}
else{
vector<int> cycle;
do{
cycle.push_back(activ.top());
activ.pop();
}while(cycle.end()[-1] != valcyc);
answer+= solve_cycle(cycle);
}
}
}
cout<< n - answer;
return 0;
}
Compilation message
polygon.cpp: In function 'int solve_cycle(std::vector<int>&)':
polygon.cpp:54:16: 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<cycle.size();i++){
| ~^~~~~~~~~~~~~
polygon.cpp: In function 'int main()':
polygon.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
72 | freopen(".in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
