Submission #288664

#TimeUsernameProblemLanguageResultExecution timeMemory
288664Haunted_CppSplit the Attractions (IOI19_split)C++17
0 / 100
86 ms9240 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 5; bool vis[MAX_N], solved = false; vector<vector<int>> g(MAX_N); vector<int> sub(MAX_N); int calc(int node, int p) { sub[node] = 1; for (auto to : g[node]) { if (to != p) { sub[node] += calc(to, node); } } return sub[node]; } vector<int> ans; int split_point = -1; void paint(int node, int p, int w, int &cnt) { if (cnt) { --cnt; ans[node] = w; } for (auto to : g[node]) { if (to == p) continue; if (to == split_point) continue; paint(to, node, w, cnt); } } int n; vector<pair<int, int>> where; void dfs(int node, int p) { const int cur = sub[node]; const int other = n - cur; bool is_valid = true; for (auto to : g[node]) { if (to == p) continue; is_valid &= (sub[to] < where[0].first); } if (!solved && is_valid && cur >= where[0].first && other >= where[0].first) { solved = true; paint(node, p, where[0].second, where[0].first); split_point = node; paint(0, -1, where[1].second, where[1].first); } for (auto to : g[node]) { if (to != p) { dfs(to, node); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { ::n = n; where.emplace_back(a, 1); where.emplace_back(b, 2); where.emplace_back(c, 3); sort(where.begin(), where.end()); //~ vector<int> in(n); ans = vector<int>(n, where[2].second); const int m = p.size(); assert(m == n - 1); for (int i = 0; i < m; i++) { int st = p[i]; int et = q[i]; g[st].emplace_back(et); g[et].emplace_back(st); } calc(0, -1); dfs(0, -1); if (!solved) for (auto &to : ans) to = 0; 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...