#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
const int maxn5 = 3e5 + 10;
int a[maxn5], req[maxn5];
int dp[2][maxn5]; // dp[0 -> khodesh nabashad/ 1 -> bashad][v]
int pd[maxn5], num[maxn5];
int sz[maxn5], parof[maxn5];
map <string, int> av;
bool mark[maxn5], incy[maxn5];
vector <int> adj[maxn5], ver, tmp;
int nn = 0, cmp[maxn5];
inline int dfs2(int v){
//cout << "hello " << v << endl;
mark[v] = true;
int cy = -1;
int u = parof[v];
cmp[v] = nn;
//cout << "ok " << v << ' ' << u << endl;
if(!mark[u]){
int z = dfs2(u);
//cout << "aha " << z << endl;
if(cy == -1)
cy = z;
}
else if(cmp[u] == cmp[v]){
cy = u;
}
//cout << ' ' << v << ' ' << cy << endl;
if(cy != -1)
incy[v] = true;
return (cy == v ? -1 : cy);
}
inline void dfs(int v){
//cout << "hello " << v << endl;
dp[0][v] = 0;
sz[v] = 1;
bool re = false;
for(auto u : adj[v]) if(!incy[u]){
dfs(u);
sz[v] += sz[u];
dp[0][v] += dp[1][u] + (sz[u] % 2);
re = true;
}
if(!re){
dp[1][v] = 0;
return;
}
dp[1][v] = maxn5;
for(auto u : adj[v]) if(!incy[u]){
int val = dp[0][v] - dp[1][u] - (sz[u] % 2);
val += dp[0][u] + (sz[u] % 2 == 0);
val++;
if(sz[v] % 2 == 1)
val--;
dp[1][v] = min(dp[1][v], val);
}
if(sz[v] % 2 == 0){
dp[0][v]--;
}
else{
dp[1][v] = min(dp[1][v], dp[0][v]);
}
//cout << v << ' ' << dp[0][v] << ' ' << dp[1][v] << endl;
return;
}
inline int find_next(int v){
return parof[v];
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
int ind = 0;
for(int i = 0; i < n; i++){
string s, t; cin >> s >> t;
if(av.find(s) == av.end())
av[s] = ind++;
if(av.find(t) == av.end())
av[t] = ind++;
adj[av[t]].pb(av[s]);
parof[av[s]] = av[t];
}
/*
for(auto it = av.begin(); it != av.end(); it++)
cout << (it -> fi) << ' ' << (it -> se) << endl;
//*/
if(n % 2 == 1)
return cout << -1 << endl, 0;
memset(mark, false, sizeof mark);
for(int i = 0; i < n; i++) if(!mark[i]){
dfs2(i);
nn++;
}
for(int i = 0; i < n; i++) if(incy[i]){
dfs(i);
}
memset(mark, false, sizeof mark);
ll ans = 0;
for(int i = 0; i < n; i++) if(incy[i] && !mark[i]){
//cout << "oh a new day! " << i << endl;
ver.clear();
int v = find_next(i);
mark[i] = true;
ver.pb(i);
while(v != i){
mark[v] = true;
ver.pb(v);
v = find_next(v);
//cout << v << ' ' << i << endl;
}
if(ver.size() == 1){
ans += dp[1][i];
if(sz[i] % 2 == 1)
ans++;
continue;
}
pd[0] = dp[1][i];
num[0] = sz[i];
for(int j = 1; j < ver.size(); j++){
int u = ver[j];
num[j] = num[j - 1] + sz[u];
pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
if(f >= 2)
val += 2;
pd[j] = min(pd[j], val);
val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
pd[j] = min(pd[j], val);
}
int cur = pd[ver.size() - 1] + (num[ver.size() - 1] % 2);
tmp.clear();
tmp.pb(ver.back());
for(auto u : ver)
tmp.pb(u);
tmp.pop_back();
ver.clear();
for(auto u : tmp)
ver.pb(u);
pd[0] = dp[1][i];
num[0] = sz[i];
for(int j = 1; j < ver.size(); j++){
int u = ver[j];
num[j] = num[j - 1] + sz[u];
pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
if(f >= 2)
val += 2;
pd[j] = min(pd[j], val);
val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
pd[j] = min(pd[j], val);
}
cur = min(cur, pd[ver.size() - 1] + (num[ver.size() - 1] % 2));
if(ver.size() == 2){
cur = min(cur, dp[0][ver[0]] + dp[0][ver[1]] + 2 * (sz[ver[0]] % 2 == 0 && sz[ver[1]] % 2 == 0));
}
ans += cur;
}
cout << ans << endl;
}
Compilation message
polygon.cpp: In function 'int main()':
polygon.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int j = 1; j < ver.size(); j++){
| ~~^~~~~~~~~~~~
polygon.cpp:157:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int j = 1; j < ver.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7628 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7628 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7628 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
7628 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7628 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7628 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7628 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
19876 KB |
Output is correct |
| 2 |
Correct |
292 ms |
21844 KB |
Output is correct |
| 3 |
Correct |
195 ms |
20576 KB |
Output is correct |
| 4 |
Correct |
222 ms |
17120 KB |
Output is correct |
| 5 |
Correct |
264 ms |
27812 KB |
Output is correct |
| 6 |
Correct |
252 ms |
19012 KB |
Output is correct |
| 7 |
Correct |
234 ms |
19052 KB |
Output is correct |
| 8 |
Correct |
254 ms |
19488 KB |
Output is correct |
| 9 |
Correct |
217 ms |
18540 KB |
Output is correct |
| 10 |
Correct |
174 ms |
17788 KB |
Output is correct |
| 11 |
Correct |
6 ms |
7628 KB |
Output is correct |
| 12 |
Correct |
6 ms |
7628 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7628 KB |
Output is correct |
| 14 |
Correct |
4 ms |
7628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7628 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7628 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7628 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
7628 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
