Submission #1210659

#TimeUsernameProblemLanguageResultExecution timeMemory
1210659Theo830Love Polygon (BOI18_polygon)C++20
0 / 100
208 ms22368 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]; 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[idx]++; for(auto x:rev[idx]){ if(!v[x]){ dfs2(x,par); } } } 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)); } 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++; } if(siz[x] != 2){ ans += siz[x] / 2; } } } 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...