Submission #712071

#TimeUsernameProblemLanguageResultExecution timeMemory
712071wenqiLove Polygon (BOI18_polygon)C++17
100 / 100
109 ms12816 KiB
// trans rights #include <bits/extc++.h> using namespace std; using ll = long long; int N; unordered_map<string, int> mp; int to[100069]; int cnt[100069]; bool taken[100069]; int main(int argc, const char *argv[]) { ios::sync_with_stdio(false); cin.tie(0); cin >> N; if (N & 1) { cout << -1; return 0; } int n = 1; for (int i = 0; i < N; i++) { string a, b; cin >> a >> b; int &ia = mp[a], &ib = mp[b]; if (not ia) ia = n++; if (not ib) ib = n++; to[ia] = ib; cnt[ib]++; } priority_queue<pair<int, int>> pq; int ans = 0; for (int i = 1; i <= N; i++) { if (i == to[i]) { } else if (i == to[to[i]]) { taken[i] = true; taken[to[i]] = true; } } for (int i = 1; i <= N; i++) { if (not taken[i]) pq.push({-cnt[i], i}); } while (pq.size()) { auto [k, i] = pq.top(); pq.pop(); if (-k != cnt[i] or taken[i]) continue; ans++; if (taken[to[i]]) { continue; } cnt[to[to[i]]]--; pq.push({-cnt[to[to[i]]], to[to[i]]}); taken[i] = taken[to[i]] = true; } cout << ans; 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...