제출 #411819

#제출 시각아이디문제언어결과실행 시간메모리
411819timmyfengSplit the Attractions (IOI19_split)C++17
0 / 100
89 ms12944 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100001; int sub[N], dsu[N], color[N]; vector<int> adj[N], span[N]; bool special[N]; int find(int u) { if (dsu[u] < 0) { return u; } else { dsu[u] = find(dsu[u]); return dsu[u]; } } bool unite(int u, int v) { u = find(u), v = find(v); if (u != v) { if (-dsu[u] > -dsu[v]) { swap(u, v); } dsu[v] += dsu[u]; dsu[u] = v; return true; } return false; } void dfs_span(int u) { for (auto c : adj[u]) { if (adj[c].empty()) { span[u].push_back(c); span[c].push_back(u); dfs_span(c); } } } void dfs_sub(int u, int p = -1) { sub[u] = 1; for (auto c : span[u]) { if (c != p) { dfs_sub(c, u); sub[u] += sub[c]; } } } int dfs_find(int u, int n, int p = -1) { for (auto c : span[u]) { if (c != p && sub[c] > n / 2) { return dfs_find(c, n, u); } } return u; } void dfs_unite(int u, int p = -1) { for (auto c : span[u]) { if (c != p) { unite(u, c); dfs_unite(c, u); } } } void dfs_color(int u, int x, int &y) { color[u] = x; --y; for (auto c : adj[u]) { if (special[c] == special[u] && color[c] == 0 && y > 0) { dfs_color(c, x, y); } } } bool visited[N]; int dfs_count(int u) { visited[u] = true; int ans = 1; for (auto c : adj[u]) { if (special[c] == special[u] && !visited[c]) { ans += dfs_count(c); } } return ans; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { fill(adj, adj + n, vector<int>()); for (int i = 0; i < (int) p.size(); ++i) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } fill(span, span + n, vector<int>()); dfs_span(0); dfs_sub(0); int root = dfs_find(0, n); fill(dsu, dsu + n, -1); for (auto u : span[root]) { dfs_unite(u, root); } int ans = -1; for (int i = 0; i < n; ++i) { if (i != root && -dsu[find(i)] >= min({a, b, c})) { ans = find(i); } } for (int i = 0; i < n && ans == -1; ++i) { for (auto j : adj[i]) { if (i != root && j != root && unite(i, j)) { if (-dsu[find(i)] >= min({a, b, c})) { ans = find(i); break; } } } } if (ans == -1) { return vector<int>(n); } for (int i = 0; i < n; ++i) { special[i] = find(i) == ans; } int x_min, x_mid; if (a <= min(b, c)) { x_min = 1; x_mid = b <= c ? 2 : 3; } else if (b <= min(a, c)) { x_min = 2; x_mid = a <= c ? 1 : 3; } else { x_min = 3; x_mid = a <= b ? 1 : 2; } int y_min = vector<int>{a, b, c}[x_min - 1]; int y_mid = vector<int>{a, b, c}[x_mid - 1]; fill(color, color + n, 0); dfs_color(-dsu[ans] <= n / 2 ? ans : root, x_min, y_min); dfs_color(-dsu[ans] <= n / 2 ? root : ans, x_mid, y_mid); fill(visited, visited + n, false); assert(dfs_count(ans) == -dsu[ans]); for (int i = 0; i < n; ++i) { if (color[i] == 0) { color[i] = x_min ^ x_mid; } } return vector<int>(color, color + 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...
#Verdict Execution timeMemoryGrader output
Fetching results...