Submission #622301

#	Time	Username	Problem	Language	Result	Execution time	Memory
622301		Jomnoi	Split the Attractions (IOI19_split)	C++17	0 / 100	76 ms	11300 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;

const int MAX_N = 1e5 + 5;

int N, M, A, B, C;
vector <int> graph[MAX_N];
vector <int> res;

void dfs(int u, int p, int a) {
	A--;
	res[u] = a;
	if(A == 0) {
		if(B > 0) {
			swap(A, B);
			a = 2;
		}
		else {
			swap(A, C);
			a = 3;
		}
	}
	for(auto v : graph[u]) {
		if(res[v] == p and A > 0) {
			dfs(v, p, a);
		}
	}
}

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);

	vector <int> tmp({A, B, C});
	sort(tmp.begin(), tmp.end());
	A = tmp[0], B = tmp[1], C = tmp[2];

	for(int i = 0; i < M; i++) {
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	int rt = 0;
	for(int i = 0; i < N; i++) {
		if(graph[i].size() == 1) {
			rt = i;
			break;
		}
	}

	dfs(rt, 0, 1);
	// for(int i = 0; i < N; i++) {
	// 	if(res[i] == 0) {
	// 		A = B;
	// 		dfs(i, 0, -1);
	// 		if(A == 0) {
	// 			A = B, B = 0;
	// 			dfs(i, -1, 2);
	// 			break;
	// 		}
	// 	}
	// }
	// for(int i = 0; i < N; i++) {
	// 	if(res[i] != 1 and res[i] != 2) {
	// 		res[i] = 3;
	// 		C--;
	// 	}
	// }
	// if(A != 0 or B != 0 or C != 0) {
	// 	fill(res.begin(), res.end(), 0);
	// }
	return res;
}

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