제출 #702130

#제출 시각아이디문제언어결과실행 시간메모리
702130Shreyan_PaliwalLove Polygon (BOI18_polygon)C++17
0 / 100
2069 ms15056 KiB
#include <iostream> #include <vector> #include <map> using namespace std; const int maxn = 1e5 + 5; int n; int par[maxn]; int vis[maxn]; vector<int> cycle_starts; vector<int> adj[maxn]; bool dfs_find_cycle(int nd) { vis[nd] = 1; // current vertex visited if (vis[par[nd]] == 0) { // if next vertex unvisited dfs_find_cycle into it if (dfs_find_cycle(par[nd])) { vis[nd] = 2; return true; } } else if (vis[par[nd]] == 1) { // if visited next vertex in current iteration cycle_starts.push_back(nd); vis[nd] = 2; return true; // back out } vis[nd] = 2; // mark current vertex visited return false; } void find_components() { for (int i = 0; i < n; i++) { if (vis[i]) continue; dfs_find_cycle(i); } } void read_input() { cin >> n; map<string, int> m; int cnt = 0; for (int i = 0; i < n; i++) { string a, b; cin >> a >> b; // if (m.find(a) == m.end()) cout << a << ' ' << cnt << endl; if (m.find(a) == m.end()) m[a] = cnt++; // if (m.find(b) == m.end()) cout << b << ' ' << cnt << endl; if (m.find(b) == m.end()) m[b] = cnt++; par[m[a]] = m[b]; adj[m[a]].push_back(m[b]); adj[m[b]].push_back(m[a]); } } int cur_root = -1; int F[maxn], G[maxn]; int f(int x, int par); int g(int x, int par); int f(int x, int par) { F[x] = 1; for (auto i : adj[x]) if (i != par && i != cur_root) F[x] += g(i, x); // cout << "f " << x << ' ' << F[x] << endl; return F[x]; } int g(int x, int par) { G[x] = f(x, par) - 1; int max_fg = 0; for (auto i : adj[x]) if (i != par && i != cur_root) max_fg = max(max_fg, f(i, x) - g(i, x)); G[x] += max_fg; // cout << "g " << x << ' ' << G[x] << endl; return G[x]; } int main() { // freopen("main.in", "r", stdin); read_input(); if (n & 1) { cout << -1 << endl; return 0; } find_components(); fill(F, F + maxn, -1); fill(G, G + maxn, -1); int sum_root_g = 0; for (auto i : cycle_starts) { // cycle starts @ i & size 1 if (i == par[i]) { cur_root = i; sum_root_g += g(i, i); } // size 2 else if (i == par[par[i]]) { // cout << sum_root_g << ' '; // optimal to take arc // i, par[i] for (auto j : adj[i]) if (j != par[i]) sum_root_g += g(j, i); for (auto j : adj[par[i]]) if (j != i) sum_root_g += g(j, par[j]); sum_root_g += 2; // cout << sum_root_g << endl; } else { // cout << i << endl; // par[i] --> ... --> i --> par[i] cur_root = par[i]; // take arc int with_arc = 1; for (auto j : adj[i]) if (j != par[i]) with_arc += g(j, i); for (auto j : adj[par[i]]) if (j != i) with_arc += g(j, par[i]); // cout << "with arc " << i << ' ' << par[i] << ' ' << with_arc << endl; int without_arc = g(par[i], i); // cout << "without arc " << i << ' ' << par[i] << ' ' << without_arc << endl; sum_root_g += max(with_arc, without_arc); } } cout << n - sum_root_g << 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...