제출 #1210499

#제출 시각아이디문제언어결과실행 시간메모리
1210499banganSplit the Attractions (IOI19_split)C++20
0 / 100
545 ms1114112 KiB
#include "split.h" using namespace std; #define X first #define Y second #define pair pair<int, int> #define pb push_back #define all(a) a.begin(), a.end() const int N = 2e5 + 4; vector<int> adj[N]; int sub[N]; int fa[N]; bool dead[N]; vector<int> ans; void prep(int v) { for (int u : adj[v]) if (u != fa[v]) { fa[u] = v; prep(u); sub[v] += sub[u]; } } void kill(int v, int id) { dead[v]=1; ans[v] = id; for (int u : adj[v]) if (u != fa[v]) kill(u, id); } void assign(int v, int cnt, int id) { if (cnt>0) ans[v] = id, cnt--; for (int u : adj[v]) if (u != fa[v] && !dead[u]) assign(u, cnt, id); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { for (int i=0; i<p.size(); i++) { adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } prep(0); vector<pair> ord{{a,1}, {b,2}, {c,3}}; sort(all(ord), [&](auto lhs, auto rhs) { return lhs.X > rhs.X; }); ans.resize(n); int v=0; for (int i=0; i<n; i++) if (sub[i]>=ord.back().X && sub[i]<sub[v]) v=i; kill(v, ord.back().Y); ord.pop_back(); if (!dead[0]) assign(0, ord.back().X, ord.back().Y); if (count(all(ans), ord.back().Y) != ord.back().X) return vector(n, 0); ord.pop_back(); for (int i=0; i<n; i++) if (!ans[i]) ans[i] = ord.back().Y; 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...