Submission #374681

#TimeUsernameProblemLanguageResultExecution timeMemory
374681moratoLove Polygon (BOI18_polygon)C++17
25 / 100
396 ms29164 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; map<string, int> id; string a[N], b[N]; vector<int> adj[N]; int prv[N], ans = 0, vis[N]; void dfs(int v) { vis[v] = 1; for (int u : adj[v]) { if (!vis[u]) { prv[u] = v; dfs(u); } else if (vis[u] == 1) { // cout << v << " -> " << u << '\n'; // cout << "ciclo: " << v << ' '; int sz = 1, cur = v; while (cur != u) { cur = prv[cur]; sz++; // cout << cur << ' '; } // cout << '\n'; ans += (sz == 2 ? 0 : (sz + 1) / 2); } } vis[v] = 2; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; id[a[i]], id[b[i]]; } if (n & 1) { cout << -1 << '\n'; return 0; } int cnt = 0; for (auto it = id.begin(); it != id.end(); it++) { it->second = ++cnt; } for (int i = 0; i < n; i++) { adj[id[a[i]]].push_back(id[b[i]]); } for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i); } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...