Submission #427014

#TimeUsernameProblemLanguageResultExecution timeMemory
427014salehSplit the Attractions (IOI19_split)C++17
11 / 100
92 ms10612 KiB
#include "split.h" #include <bits/stdc++.h> #define ft first #define sd second using namespace std; typedef pair<int, int> pii; const int MAXN = 100 * 1000 + 23; int zz = -1, cc, sz[MAXN], par[MAXN]; vector<int> res; bitset<MAXN> mark; vector<int> g[MAXN]; void dfsa(int v) { mark[v] = true; zz = v; cc--; for (auto i : g[v]) if (!mark[i] && cc != 0) dfsa(i); } int sfs(int v = 0, int p = -1) { par[v] = p; for (auto i : g[v]) if (i != p) sz[v] += sfs(i, v); return ++sz[v]; } void mfs(int v, int p, int c) { res[v] = c; for (int i : g[v]) if (i != p) mfs(i, v, c); } void cfs(int v, int c) { mark[v] = true; cc--; res[v] = c; for (auto i : g[v]) if (!mark[i] && cc != 0) cfs(i, c); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = p.size(); for (int i = 0; i < m; i++) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]); if (a == 1) { for (int i = 0; i < n; i++) res.push_back(3); cc = b + 1; dfsa(0); for (int i = 0; i < n; i++) if (mark[i]) res[i] = 2; res[zz] = 1; return res; } if (m == n) { for (int i = 0; i < n; i++) res.push_back(0); cc = a; cfs(0, 1); for (int i = 0; i < n; i++) if (!mark[i]) { cc = b; cfs(i, 2); break; } for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = 3; return res; } if (m == n - 1) { exit(3); for (int i = 0; i < n; i++) res.push_back(0); vector<pii> o = {{a, 1}, {b, 2}, {c, 3}}; sort(o.begin(), o.end()); int f = min({a, b, c}), g = max({min(a, b), min(b, c), min(c, a)}); sfs(); for (int i = 1; i < n; i++) if (sz[i] >= f && n - sz[a] >= g) { cc = f; mfs(i, par[i], o[0].sd); cc = g; mfs(par[i], i, o[1].sd); for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd; break; } else if (sz[i] >= g && n - sz[a] >= f) { cc = g; mfs(i, par[i], o[1].sd); cc = f; mfs(par[i], i, o[0].sd); for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd; break; } return res; } return res; } //int main() {}
#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...