Submission #591705

#TimeUsernameProblemLanguageResultExecution timeMemory
591705lumibonsSplit the Attractions (IOI19_split)C++17
18 / 100
101 ms17484 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; int n, s[3], t[3], cs[3], c[100100]; vector<int> r, e[100100]; int dfs(int i) { r[i] = -1; c[i] = 1; for (int j : e[i]) if (!r[j]) { int k = dfs(j); c[i] += c[j]; if (c[i] >= s[0]) return k < 0 ? i : k; } r[i] = -2; return c[i] >= s[0] ? i : -1; } void dfst(int i, int cr, int k) { if (cs[k] == s[k]) return; r[i] = t[k]; cs[k]++; for (int j : e[i]) if (r[j] == cr) dfst(j, cr, k); } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n = N; s[0] = a; s[1] = b; s[2] = c; t[0] = 1; t[1] = 2; t[2] = 3; for (int i : {0, 1, 0}) if (s[i] > s[i + 1]) swap(s[i], s[i + 1]), swap(t[i], t[i + 1]); for (int i = 0; i < (int) p.size(); i++) e[p[i]].push_back(q[i]), e[q[i]].push_back(p[i]); r.resize(n); int k = dfs(0); if (k != 0) { r[k] = -3; for (int i = 0; i < n; i++) if (r[i] == 0) r[i] = -1; dfst(0, -1, 1); for (int i = 0; i < n; i++) if (r[i] == t[1]) for (int j : e[i]) if (r[j] == -2) dfst(j, -2, 1); r[k] = -2; dfst(k, -2, 0); } if (cs[0] != s[0] || cs[1] != s[1]) r.assign(n, 0); else for (int i = 0; i < n; i++) r[i] = r[i] < 1 ? t[2] : r[i]; return r; }
#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...