Submission #1202046

#TimeUsernameProblemLanguageResultExecution timeMemory
1202046onbertSplit the Attractions (IOI19_split)C++20
40 / 100
64 ms29888 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n, m; vector<pair<int,int>> vec; int a, b; vector<int> adj[maxn]; vector<int> adj1[maxn]; bool vis[maxn]; int fa[maxn], sz[maxn]; void dfs(int u) { sz[u] = vis[u] = 1; for (int v:adj[u]) if (!vis[v]) { fa[v] = u; adj1[u].push_back(v); adj1[v].push_back(u); dfs(v); sz[u] += sz[v]; } } vector<int> ord; void dfs1(int u, int p) { ord.push_back(u); for (int v:adj1[u]) if (v != p) dfs1(v, u); } vector<int> ans; int root = -1; int dsu[maxn], nodes[maxn]; int rt(int u) { if (dsu[u] == u) return u; return dsu[u] = rt(dsu[u]); } void merge(int u, int v) { u = rt(u), v = rt(v); if (u != v) { nodes[v] += nodes[u]; dsu[u] = v; } } int anc[maxn]; void dfs2(int u, int p) { for (int v:adj1[u]) if (v != p) { anc[v] = anc[u]; dfs2(v, u); } } vector<int> adj2[maxn]; void dfs3(int u, int p) { ord.push_back(u); for (int v:adj2[u]) if (v != p) dfs3(v, u); } int nodecnt; void dfs5(int u, int p) { if (nodecnt < a) ans[u] = vec[0].second, nodecnt++; for (int v:adj1[u]) if (v != p) dfs5(v, u); } void dfs4(int u) { ord.push_back(u); vis[u] = 1; for (int v:adj[u]) if (!vis[v] && !ans[v]) dfs4(v); } vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) { n = N, m = p.size(); vec = {{A, 1}, {B, 2}, {C, 3}}; sort(vec.begin(), vec.end()); for (int i=0;i<m;i++) {adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]);} fa[0] = -1; dfs(0); a = vec[0].first, b = vec[1].first; ans.resize(n); for (int i=0;i<n;i++) ans[i] = 0; for (int i=0;i<n;i++) { if (a <= sz[i] && sz[i] <= n-a) { if (sz[i] <= n-b) { for (int j=0;j<n;j++) ans[j] = vec[2].second; ord.clear(); dfs1(i, fa[i]); for (int j=0;j<a;j++) ans[ord[j]] = vec[0].second; ord.clear(); dfs1(fa[i], i); for (int j=0;j<b;j++) ans[ord[j]] = vec[1].second; } else { for (int j=0;j<n;j++) ans[j] = vec[2].second; ord.clear(); dfs1(i, fa[i]); for (int j=0;j<b;j++) ans[ord[j]] = vec[1].second; ord.clear(); dfs1(fa[i], i); for (int j=0;j<a;j++) ans[ord[j]] = vec[0].second; } return ans; } } for (int i=0;i<n;i++) if (n - sz[i] < a) { bool flag = true; for (int v:adj1[i]) if (v != fa[i] && sz[v] >= a) flag = false; if (flag) root = i; } for (int v:adj1[root]) { anc[v] = v; dfs2(v, root); nodes[v] = sz[v]; } for (int i=0;i<n;i++) dsu[i] = i; for (int i=0;i<m;i++) if (p[i] != root && q[i] != root) { int u = anc[p[i]], v = anc[q[i]]; int U = rt(u), V = rt(v); if (U == V) continue; merge(U, V); adj2[U].push_back(V); adj2[V].push_back(U); if (nodes[V] >= a) { ord.clear(); dfs3(V, -1); nodecnt = 0; for (int j:ord) dfs5(j, root); ord.clear(); for (int j=0;j<n;j++) vis[j] = 0; dfs4(root); for (int j=0;j<b;j++) ans[ord[j]] = vec[1].second; for (int j=0;j<n;j++) if (!ans[j]) ans[j] = vec[2].second; return ans; } } return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...