Submission #434015

#TimeUsernameProblemLanguageResultExecution timeMemory
434015AmineTrabelsiLove Polygon (BOI18_polygon)C++14
21 / 100
245 ms9312 KiB
#include "bits/stdc++.h" using namespace std; // Hi int main(){ ios::sync_with_stdio(0);cin.tie(0); int n; cin>>n; vector<int> go(n); map<string,int> mp; int nxt = 0; vector<pair<int,int>> edges; for(int i=0;i<n;i++){ string s,t; cin>>s>>t; int first = 0,second = 0; if(mp.find(s) != mp.end()){ first = mp[s]; }else{ first = nxt; mp[s] = nxt++; } if(mp.find(t) != mp.end()){ second = mp[t]; }else{ second = nxt; mp[t] = nxt++; } edges.push_back({first,second}); } vector<int> perm; if(n&1){ cout << -1 << endl; return 0; } auto good = [&](){ vector<bool> vis(n+1,0); for(int i=0;i<n;i++){ if(go[i] == i)return false; if(go[i] != -1){ if(go[go[i]] != -1 && go[go[i]] != i)return false; if(vis[go[i]])return false; vis[go[i]] = 1; } } return true; }; int ans = 1000000009; for(int i=0;i<(1 << n);i++){ int cnt = n; go.assign(n,-1); for(int j=0;j<n;j++){ if(i & (1<<j)){ go[edges[j].first] = edges[j].second; cnt--; } } /* for(auto x:go)cout << x<<" "; cout<<'\n';*/ if(good()){ /* for(auto x:go)cout << x<<" "; cout<<'\n';*/ ans = min(ans,cnt); } } cout << ans << '\n'; 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...