Submission #622571

#	Time	Username	Problem	Language	Result	Execution time	Memory
622571		Jomnoi	Split the Attractions (IOI19_split)	C++17	40 / 100	79 ms	17972 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
 
const int MAX_N = 1e5 + 5;
const int INF = 1e9 + 7;
 
int N, M, A, B, C;
int sz[MAX_N];
vector <int> graph[MAX_N];
vector <int> res;
bool ok = false;
 
void dfs(int u, int p, int a, int &A) {
	A--;
	res[u] = a;
	for(auto v : graph[u]) {
		if(v != p and res[v] == 0 and A > 0) {
			dfs(v, u, a, A);
		}
	}
}

int dfs2(int u, int p) {
	if(ok == true) {
		return -INF;
	}
	
	sz[u] = 1;
	for(auto v : graph[u]) {
		if(v != p) {
			sz[u] += dfs2(v, u);
		}
	}

	if(sz[u] >= A) {
		if(N - sz[u] >= B) {
			dfs(u, p, 1, A);
			dfs(p, u, 2, B);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 3;
				}
			}
			ok = true;
			return -INF;
		}
		if(N - sz[u] >= C) {
			dfs(u, p, 1, A);
			dfs(p, u, 3, C);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 2;
				}
			}
			ok = true;
			return -INF;
		}
	}
	if(sz[u] >= B) {
		if(N - sz[u] >= A) {
			dfs(u, p, 2, B);
			dfs(p, u, 1, A);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 3;
				}
			}
			ok = true;
			return -INF;
		}
		if(N - sz[u] >= C) {
			dfs(u, p, 2, B);
			dfs(p, u, 3, C);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 1;
				}
			}
			ok = true;
			return -INF;
		}
	}
	if(sz[u] >= C) {
		if(N - sz[u] >= A) {
			dfs(u, p, 3, C);
			dfs(p, u, 1, A);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 2;
				}
			}
			ok = true;
			return -INF;
		}
		if(N - sz[u] >= B) {
			dfs(u, p, 3, C);
			dfs(p, u, 2, B);
			for(int i = 0; i < N; i++) {
				if(res[i] == 0) {
					res[i] = 1;
				}
			}
			ok = true;
			return -INF;
		}
	}
	return sz[u];
}
 
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
	N = n, M = p.size(), A = a, B = b, C = c;
	res.resize(N, 0);
 
	for(int i = 0; i < M; i++) {
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	if(M == N - 1) {
		dfs2(0, -1);
	}
	else {
		int rt = 0;
		for(int i = 0; i < N; i++) {
			if(graph[i].size() == 1) {
				rt = i;
				break;
			}
		}
	
		dfs(rt, -1, 2, B);
		for(int i = 0; i < N; i++) {
			if(res[i] == 0) {
				dfs(i, -1, 1, A);
				break;
			}
		}
		for(int i = 0; i < N; i++) {
			if(res[i] == 0) {
				res[i] = 3;
			}
		}
	}
	return res;
}

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