Submission #1091369

#TimeUsernameProblemLanguageResultExecution timeMemory
1091369MateiKing80Love Polygon (BOI18_polygon)C++14
100 / 100
156 ms11928 KiB
#include <bits/stdc++.h> using namespace std; int p[100025], n, grad[100025]; map<string, int> nume; bool vis[100025]; queue<int> q; int main () { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i < n; i ++) { string s, t; cin >> s >> t; if(!nume.count(s)) nume[s] = (int)nume.size(); if(!nume.count(t)) nume[t] = (int)nume.size(); p[nume[s]] = nume[t]; grad[nume[t]] ++; } if(n % 2 == 1) { cout << -1; return 0; } int ans = 0; for(int i = 0; i < n; i ++) if (grad[i] == 0) q.push(i); while (!q.empty()) { auto k = q.front(); q.pop(); if(grad[k] != 0) continue; if(p[p[k]] != p[k] && p[p[p[k]]] == p[k]) continue; if(p[p[k]] == p[k]) { p[p[k]] = k; grad[k] ++; grad[p[k]] --; ans ++; continue; } ans ++; grad[p[p[k]]] --; if(grad[p[p[k]]] == 0) q.push(p[p[k]]); p[p[k]] = k; grad[k] ++; } for(int i = 0; i < n; i ++) if(grad[i] == 0) { ans++; grad[i] = 2; grad[p[i]] --; } for(int i = 0; i < n; i ++) if(grad[i] == 1 && !vis[i]) { vector<int> t = {i}; vis[i] = 1; int u = p[i]; while(u != i) { t.push_back(u); vis[u] = 1; u = p[u]; } if(t.size() == 2) continue; int z = t.size(); ans += (z + 1) / 2; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...