Submission #1202038

#TimeUsernameProblemLanguageResultExecution timeMemory
1202038onbertSplit the Attractions (IOI19_split)C++20
18 / 100
66 ms29884 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n, m; 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); } void dfs4(int u) { ord.push_back(u); vis[u] = 1; for (int v:adj[u]) if (!vis[v] && !ans[v]) dfs4(v); } int test; set<int> S; void dfs5(int u) { test++, vis[u] = 1; S.insert(u); for (int v:adj[u]) if (!vis[v]) dfs5(v); } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n = N, m = p.size(); vector<pair<int,int>> 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:adj[i]) if (sz[v] >= a) flag = false; if (flag) root = i; } assert(root != -1); for (int i=0;i<n;i++) vis[i] = 0; vis[root] = 1; int cnt = 0; for (int i=0;i<n;i++) if (!vis[i]) { test = 0; dfs5(i); cnt++; } // assert(cnt == adj[root].size()); return ans; // 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); // int cnt = 0; // for (int j:ord) { // ans[j] = vec[0].second; // cnt += sz[j]; // if (cnt >= a) break; // } // for (int j=0;j<n;j++) if (j != root && ans[anc[j]]) { // ans[j] = vec[0].second; // } // 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; // } // } }
#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...