Submission #950615

#	Time	Username	Problem	Language	Result	Execution time	Memory
950615		qin	Split the Attractions (IOI19_split)	C++17	40 / 100	86 ms	19540 KiB

split

#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

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36