Submission #1210673

#TimeUsernameProblemLanguageResultExecution timeMemory
1210673Theo830Love Polygon (BOI18_polygon)C++20
0 / 100
217 ms30196 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training vector<vector<ll> >adj,rev,adj2; bool v[100005] = {0}; ll p[100005]; ll siz[100005] = {0}; ll dp[100005][3]; vector<ll>order; void dfs(ll idx){ v[idx] = 1; for(auto x:adj[idx]){ if(!v[x]){ dfs(x); } } order.pb(idx); } void dfs2(ll idx,ll par){ v[idx] = 1; p[idx] = par; siz[par]++; for(auto x:rev[idx]){ if(!v[x]){ dfs2(x,par); } } } ll solve(ll idx,ll c){ if(dp[idx][c] != -1){ return dp[idx][c]; } ll ans; if(c == 0 || c == 2){ ans = 1 ^ (c/2); for(auto x:adj2[idx]){ ans += min(solve(x,0),solve(x,1)); } } else{ ans = 1; ll sum = 0; ll mini = INF; for(auto x:adj2[idx]){ sum += min(solve(x,0),solve(x,1)); mini = min(mini,solve(x,2) - min(solve(x,0),solve(x,1))); } ans += sum + mini; } return dp[idx][c] = ans; } int main(void){ ll n; cin>>n; if(n % 2 == 1){ cout<<-1<<"\n"; return 0; } map<string,ll>mp; ll pos = 1; adj.assign(n+5,vector<ll>()); adj2.assign(n+5,vector<ll>()); rev.assign(n+5,vector<ll>()); vector<ii>ed; f(i,0,n){ string a,b; cin>>a>>b; ll x,y; if(!mp.count(a)){ mp[a] = pos; pos++; } if(!mp.count(b)){ mp[b] = pos; pos++; } x = mp[a]; y = mp[b]; adj[x].pb(y); rev[y].pb(x); ed.pb(ii(x,y)); } f(i,1,n+1){ if(!v[i]){ dfs(i); } } reverse(all(order)); f(i,0,n+5){ v[i] = 0; } ll ans = 0; for(auto x:order){ if(!v[x]){ dfs2(x,x); if(siz[x] != 2){ ans += siz[x] / 2; } } } ll co[n+5] = {0}; for(auto x:ed){ ll i = p[x.F],j = p[x.S]; if(siz[i] % 2 == 1 && siz[j] % 2 == 1 && i != j){ adj2[j].pb(i); co[i]++; } } memset(dp,-1,sizeof dp); f(i,1,n+1){ if(!co[i] && !adj2[i].empty()){ ans += min(solve(i,0),solve(i,1)); } } 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...