Submission #969755

#TimeUsernameProblemLanguageResultExecution timeMemory
969755Darren0724Love Polygon (BOI18_polygon)C++17
100 / 100
236 ms12640 KiB
#include<bits/stdc++.h> using namespace std; #define endl '\n' const int N=100005; map<string,int> m; vector<int> vis(N); vector<int> v(N,-1),in(N),inq(N); inline int id(string s){ if(m.count(s)){ return m[s]; } int p=m.size(); //cout<<s<<' '<<p<<endl; 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(); inq[p]++; //cout<<p<<endl; in[v[p]]--; if(in[v[p]]==0){ q.push(v[p]); } if(vis[p]){ continue; } ans++; vis[p]=vis[v[p]]=1; } for(int i=0;i<n;i++){ if(vis[i])continue; int sz=0,f=v[i]; vector<int> a(1,vis[i]); vis[i]=1; while(f!=i){ a.push_back(vis[f]); vis[f]=1; f=v[f]; } int idx=0; for(int i=0;i<a.size();i++){ if(a[i]==1)idx=(i+1)%(int)a.size(); } for(int i=0;i<a.size();i++){ //cout<<a[idx]<<endl; if(a[idx]==0)sz++; else ans+=(sz+1)/2,sz=0; idx++; idx%=(int)a.size(); } //assert(sz==1); ans+=(sz+1)/2; } cout<<ans<<endl; return 0; }

Compilation message (stderr)

polygon.cpp: In function 'int32_t main()':
polygon.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
polygon.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...