Submission #1031501

#TimeUsernameProblemLanguageResultExecution timeMemory
1031501codexistentLove Polygon (BOI18_polygon)C++14
50 / 100
378 ms33752 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define FOR(i, a, b) for(int i = a; i <= b; i++) #define f first #define s second int n, ec[MAXN]; string st[MAXN], nx[MAXN]; map<string, int> idx; set<int> adj[MAXN]; set<pair<int, int>> se; bool d[MAXN]; int main(){ cin >> n; FOR(i, 1, n) ec[i] = 0; FOR(i, 1, n){ cin >> st[i]; idx.insert({st[i], i}); cin >> nx[i]; } if(n % 2) { cout << -1 << endl; return 0; } int r = 0; FOR(i, 1, n){ d[i] = (idx[nx[idx[nx[i]]]] == i && idx[nx[i]] != i); } FOR(i, 1, n){ if(i == idx[nx[i]] || d[i] || d[idx[nx[i]]]) continue; adj[i].insert(idx[nx[i]]); adj[idx[nx[i]]].insert(i); } int ct = 0; FOR(i, 1, n) if(!d[i]) ct++, se.insert({(int)adj[i].size(), i}); while(ct && se.size()){ auto si = *se.begin(); d[si.s] = true, ct--; if(si.f == 0){ r++; }else{ int j = 0, jmn = INT_MAX; for(int i : adj[si.s]){ if(jmn > (int)adj[i].size()) j = i, jmn = (int)adj[i].size(); } r++; se.erase({jmn, j}); for(int j2 : adj[j]){ se.erase({(int)adj[j2].size(), j2}); adj[j2].erase(j); se.insert({(int)adj[j2].size(), j2}); } } for(int i2 : adj[si.s]) { se.erase({(int)adj[i2].size(), i2}); adj[i2].erase(si.s); se.insert({(int)adj[i2].size(), i2}); } se.erase(se.begin()); } cout << r << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...