제출 #718325

#제출 시각아이디문제언어결과실행 시간메모리
718325bebraSplit the Attractions (IOI19_split)C++17
0 / 100
524 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]; } if (sz[v] >= val[order[0]] && n - sz[v] >= val[order[1]]) { block[v] = true; int curr_cnt1 = val[order[0]]; int curr_cnt2 = val[order[1]]; dfs_color(v, -1, order[0], curr_cnt1); dfs_color(0, -1, order[1], curr_cnt2); return true; } if (sz[v] >= val[order[1]] && n - sz[v] >= val[order[0]]) { block[v] = true; int curr_cnt1 = val[order[0]]; int curr_cnt2 = val[order[1]]; dfs_color(v, -1, order[1], curr_cnt2); dfs_color(0, -1, order[0], curr_cnt1); 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...