This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5+5;
int arr[N], dp[N][2], dp2[N][2], dsu[N];
vector<int> adj[N];
int find(int u){
return dsu[u]==u ? u : dsu[u] = find(dsu[u]);
}
void unite(int u, int v){
u = find(u), v = find(v);
if(u==v) return;
dsu[u] = v;
}
void dfs(int u, int p, int no = -1){
int sum = 0, sum2 = 0;
for(auto v : adj[u]){
if(v==p) continue;
dfs(v,u,no);
dp[u][0] += max(dp[v][0],dp[v][1]);
dp2[u][0] += max(dp2[v][0],dp2[v][1]);
}
for(auto v : adj[u]){
if(v==p) continue;
dp[u][1] = max(dp[u][1],dp[u][0]-max(dp[v][0],dp[v][1])+dp[v][0]+1);
if(u!=no) dp2[u][1] = max(dp2[u][1],dp2[u][0]-max(dp2[v][0],dp2[v][1])+dp2[v][0]+1);
}
if(u==no) dp2[u][1] = -1e18;
}
int idx;
map<string,int> m;
int assign(string x){
if(m.find(x)==m.end()){
m[x] = idx++;
}
return m[x];
}
signed main(){
fastio
iota(dsu,dsu+N,0);
int n;
cin >> n;
vector<pair<int,int>> edges;
for(int i = 0;i < n;i++){
string a,b;
cin >> a >> b;
int x = assign(a);
int y = assign(b);
arr[x] = y;
if(find(x)!=find(y)) unite(x,y), adj[x].push_back(y), adj[y].push_back(x);
else edges.push_back({x,y});
}
if(n%2){
cout << -1 << "\n";
return 0;
}
int ans = n;
for(auto [x,y] : edges){
dfs(x,x,y);
if(x!=y) ans -= max({dp[x][0],dp[x][1],dp2[x][0]+(arr[x]==y && arr[y]==x ? 2 : 1)});
else ans -= max(dp[x][0],dp[x][1]);
}
cout << ans << "\n";
}
Compilation message (stderr)
polygon.cpp: In function 'void dfs(long long int, long long int, long long int)':
polygon.cpp:24:9: warning: unused variable 'sum' [-Wunused-variable]
24 | int sum = 0, sum2 = 0;
| ^~~
polygon.cpp:24:18: warning: unused variable 'sum2' [-Wunused-variable]
24 | int sum = 0, sum2 = 0;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |