Submission #485556

#TimeUsernameProblemLanguageResultExecution timeMemory
485556sam571128Love Polygon (BOI18_polygon)C++17
0 / 100
229 ms17828 KiB
#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 visited[N], arr[N], sz[N], visited2[N], check[N], dp[N][2]; vector<int> adj[N]; void dfs(int u){ if(arr[u]==u) check[u] = 1; sz[u] = 1; visited[u] = 1; for(auto v : adj[u]){ if(visited[v]) continue; dfs(v); sz[u] += sz[v]; check[u] |= check[v]; } } void dfs2(int u, int p){ visited[u] = 1; sz[u] = 1; dp[u][0] = 0; dp[u][1] = 1; int sum = 0; for(auto v : adj[u]){ if(v==p) continue; dfs2(v,u); sum += dp[v][0]; sz[u] += sz[v]; } for(auto v : adj[u]){ if(v==p) continue; dp[u][0] = max({sum-dp[v][0]+dp[v][1],dp[v][0],sum,dp[u][0]}); dp[u][1] = sum+1; } } 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 int n; cin >> n; 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(x==y) continue; adj[x].push_back(y); adj[y].push_back(x); } if(n%2){ cout << -1 << "\n"; return 0; } int ans = 0; for(int i = 0; i < n; i++){ if(arr[i]==i){ dfs2(i,i); ans += sz[i]-dp[i][0]; if(adj[i].size()==0) ans++; } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...