제출 #950615

#제출 시각아이디문제언어결과실행 시간메모리
950615qinSplit the Attractions (IOI19_split)C++17
40 / 100
86 ms19540 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ssize(x) int(x.size()) #define pn printf("\n") #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define vv vector using namespace std; typedef long long ll; typedef pair<int, int> pii; int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; struct graph{ vv<vv<int>> bg, g; vv<int> vis, sz, col; void init(int n){ bg.resize(n), vis.resize(n), g.resize(n), sz.resize(n, 0), col.resize(n, 0); } void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); } void add_edge_g(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); } void get_tree(int x){ vis[x] = 1; for(int u : bg[x]) if(!vis[u]) add_edge_g(u, x), get_tree(u); } void dfs_sz(int x, int par){ sz[x] = 1; for(int u : g[x]) if(u != par) dfs_sz(u, x), sz[x] += sz[u]; } int find_centroid(int x, int par, int &n){ int ret = x; for(int u : g[x]) if(u != par && sz[u] > n/2) ret = find_centroid(u, x, n); return ret; } void dfs_col(int x, int par, int k, int kol){ col[x] = kol; --k; for(int u : g[x]) if(u != par && !col[u] && k){ if(k <= sz[u]) dfs_col(u, x, k, kol), k = 0; else dfs_col(u, x, sz[u], kol), k -= sz[u]; } } }; vv<int> find_split(int n, int a, int b, int c, vv<int> p, vv<int> q){ int A = 1, B = 2, C = 3; if(a > b) swap(a, b), swap(A, B); if(b > c) swap(b, c), swap(B, C); if(a > b) swap(a, b), swap(A, B); int m = ssize(p); graph g; g.init(n); for(int i = 0; i < m; ++i) g.add_edge_b(p[i], q[i]); g.get_tree(0); g.dfs_sz(0, -1); int x = g.find_centroid(0, -1, n); g.dfs_sz(x, -1); bool good = 0; //~ printf("%d\n", x); for(int u : g.g[x]) if(a <= g.sz[u]){ g.dfs_col(u, x, a, A), good = 1; break; } if(good){ g.dfs_col(x, -1, b, B); for(int i = 0; i < n; ++i) if(!g.col[i]) g.col[i] = C; } return g.col; } #ifdef LOCAL int main(){ int T = 1; for(++T; --T; ){ int n, m, a, b, c; scanf("%d%d%d%d%d", &n, &m, &a, &b, &c); vv<int> p(m), q(m); for(int i = 0; i < m; ++i) scanf("%d%d", &p[i], &q[i]); vv<int> res = find_split(n, a, b, c, p, q); for(int u : res) printf("%d ", u); pn; } return 0; } #endif
#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...