제출 #718333

#제출 시각아이디문제언어결과실행 시간메모리
718333bebraSplit the Attractions (IOI19_split)C++17
22 / 100
465 ms1048576 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define dbg(x) cerr << #x << ": " << x << endl; const int MAX_N = 1e5 + 5; vector<int> g[MAX_N]; int color[MAX_N]; bool block[MAX_N]; int sz[MAX_N]; int n; int val[3]; int order[3]; void dfs_color(int v, int p, int c, int& cnt) { if (cnt == 0) return; --cnt; color[v] = c; for (auto u : g[v]) { if (u == p || block[u]) continue; dfs_color(u, v, c, cnt); } } bool dfs_calc(int v = 0, int p = -1) { sz[v] = 1; for (auto u : g[v]) { if (u == p) continue; if (dfs_calc(u, v)) return true; sz[v] += sz[u]; } for (int t = 0; t <= 1; ++t) { if (sz[v] >= val[order[t]] && n - sz[v] >= val[order[t ^ 1]]) { block[v] = true; int curr_cnt1 = val[order[t]]; int curr_cnt2 = val[order[t ^ 1]]; dfs_color(v, p, order[t], curr_cnt1); dfs_color(0, -1, order[t ^ 1], curr_cnt2); return true; } } return false; } vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) { n = _n; int m = p.size(); for (int i = 0; i < m; ++i) { int u = p[i]; int v = q[i]; g[u].push_back(v); g[v].push_back(u); } val[0] = a; val[1] = b; val[2] = c; iota(order, order + 3, 0); sort(order, order + 3, [&](int lhs, int rhs) { return order[lhs] < order[rhs]; }); fill_n(color, n, order[2]); vector<int> res(n); if (!dfs_calc()) { return res; } for (int i = 0; i < n; ++i) { res[i] = color[i] + 1; } return res; } // int main() { // int m; // cin >> n >> m; // int a, b, c; // cin >> a >> b >> c; // vector<int> p(m), q(m); // for (int i = 0; i < m; ++i) { // cin >> p[i] >> q[i]; // } // for (auto x : find_split(n, a, b, c, p, q)) { // cout << x << ' '; // } // cout << '\n'; // }
#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...