Submission #830623

#TimeUsernameProblemLanguageResultExecution timeMemory
830623JohannLove Polygon (BOI18_polygon)C++14
100 / 100
155 ms11504 KiB
#include <bits/stdc++.h> using namespace std; #define vb vector<bool> #define vi vector<int> #define vvi vector<vi> int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; // ungerade fertig if (n % 2 == 1) { cout << -1; return 0; } map<string, int> namen; vi beziehungen(n); vi degree(n); // Grad des Knoten δ+ und δ- string sa, sb; int a, b; int idx = 0; for (int j = 0; j < n; j++){ cin >> sa >> sb; if (namen.count(sa) == 0) { namen[sa] = idx; idx++; } if (namen.count(sb) == 0) { namen[sb] = idx; idx++; } a = namen[sa]; b = namen[sb]; beziehungen[a] = b; degree[b]++; } // for (map<string, int>::iterator it = namen.begin(); it != namen.end(); ++it) { cout << it->first << " = " << it->second << endl; } // for (int i = 0; i < n; i++){ cout << i << " --> " << beziehungen[i] << " (" << degree[i] << endl; } // Aussortieren, wer in einer Beziehung ist // Knoten mit geringsten Grad finden // -> Grad = 1: Erstell Beziehung mit Nachbarn int new_edges = 0; queue<int> q; vb inRelation(n, false); for (int i = 0; i < n; ++i) { if (beziehungen[i] != i && i == beziehungen[beziehungen[i]]) inRelation[i] = true; if (degree[i] == 0) q.push(i); } while (!q.empty()) { int s = q.front(); q.pop(); if (inRelation[s]) continue; int t = beziehungen[s]; if (inRelation[t]) { --degree[t]; ++degree[s]; inRelation[s] = true; ++new_edges; } else { int u = beziehungen[t]; --degree[u]; ++degree[s]; ++new_edges; inRelation[s] = inRelation[t] = true; if (degree[u] == 0) q.push(u); } } // cout << endl << "Herumgespielt" << endl; for (int i = 0; i < n; i++){ cout << i << " --> " << beziehungen[i] << " (" << degree[i] << endl; } cout << endl; // -> Grad = 2: Eulerkreise, größer als 2: verbleibende Knoten auf Beziehung überprüfen, dann 0 Kanten, sonst 1 pro Person // -> grad >= 3: unmöglich, wegen Schubfach int clen, running_neighbor; for (int i = 0; i < n; i++){ // falls in Beziehung: keine Umkopplung if (inRelation[i]) continue; // andernfalls - find cycle length clen = 0; running_neighbor = i; do { inRelation[running_neighbor] = true; running_neighbor = beziehungen[running_neighbor]; ++clen; } while(running_neighbor != i); new_edges += (clen + 1) / 2; } cout << new_edges << endl; 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...