Submission #969707

#TimeUsernameProblemLanguageResultExecution timeMemory
969707Darren0724Love Polygon (BOI18_polygon)C++17
0 / 100
209 ms21840 KiB
#include<bits/stdc++.h> using namespace std; const int N=100005; map<string,int> m; vector<int> vis(N),deg(N); vector<int> v(N,-1),in(N); inline int id(string s){ if(m.count(s)){ return m[s]; } int p=m.size(); m[s]=p; return p; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; if(n&1){ cout<<-1<<endl; return 0; } for(int i=0;i<n;i++){ string a,b;cin>>a>>b; v[id(a)]=id(b); in[id(b)]++; if(v[id(b)]==id(a)&&a!=b){ vis[id(a)]=vis[id(b)]=1; } } int ans=0; queue<int> q; for(int i=0;i<n;i++){ if(in[i]==0){ q.push(i); } } while(q.size()){ int p=q.front(); q.pop(); //cout<<p<<endl; deg[v[p]]--; if(deg[v[p]]==0){ q.push(v[p]); } if(vis[p]||vis[v[p]]){ continue; } ans++; vis[p]=vis[v[p]]=1; } for(int i=0;i<n;i++){ if(vis[i])continue; int sz=0,f=i; while(vis[f]==0){ sz++; vis[f]=1; f=v[f]; } assert(sz==1); ans+=(sz+1)/2; } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...