Submission #904839

#TimeUsernameProblemLanguageResultExecution timeMemory
904839simona1230Love Polygon (BOI18_polygon)C++17
100 / 100
210 ms11576 KiB
#include <bits/stdc++.h> using namespace std; int n,names=1; map<string,int> mp; int nxt[100001],in[100001]; void read() { cin>>n; for(int i=1; i<=n; i++) { string a,b; cin>>a>>b; if(!mp[a])mp[a]=names++; if(!mp[b])mp[b]=names++; nxt[mp[a]]=mp[b]; in[mp[b]]++; if(a==b)nxt[mp[a]]=0; } if(n%2==1) { cout<<"-1"<<endl; exit(0); } } int used[100001]; queue<int> q; void solve() { for(int i=1;i<=n;i++) { if(in[i]==0) q.push(i); } int cnt=0,ans=0; while(q.size()) { int ver=q.front(); q.pop(); int a=nxt[ver]; int b=nxt[a]; if(nxt[b]==a)continue; in[b]--; if(in[b]==0)q.push(b); nxt[a]=ver; in[ver]++; ver=b; ans++; } for(int i=1; i<=n; i++) { if(in[i]==0||nxt[i]==0) { ans++; continue; } if(used[i]||nxt[nxt[i]]==i)continue; int len=1,ver=i; //cout<<i<<endl; while(nxt[ver]!=i) { //cout<<ver<<endl; len++; ver=nxt[ver]; used[ver]=1; } ans+=len/2+len%2; } cout<<ans<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); read(); solve(); return 0; }

Compilation message (stderr)

polygon.cpp: In function 'void solve()':
polygon.cpp:39:9: warning: unused variable 'cnt' [-Wunused-variable]
   39 |     int cnt=0,ans=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...