Submission #1187059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187059		hamzabc	Split the Attractions (IOI19_split)	C++20	40 / 100	59 ms	21832 KiB

split

#include "split.h"
#include <bits/stdc++.h>


using namespace std;
#define sp << " " <<


vector<vector<int>> graph, tree;
vector<int> sbtree;
vector<bool> vis;
vector<int> res;


void dfs1(int n){
	if (vis[n])
		return;
	vis[n] = true;
	for (auto go : graph[n]){
		if (vis[go])
			continue;
		tree[n].push_back(go);
		dfs1(go);
		sbtree[n] += sbtree[go];
	}
}

int dfs2(int a, int color, int say){
	if (res[a] || say == 0)
		return say;
	res[a] = color;
	say--;
	if (say == 0)
		return 0;
	for (auto go : tree[a]){
		say = dfs2(go, color, say);
		if (say == 0)
			return 0;
	}
	return say;
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = p.size();
	res.resize(n);
	fill(res.begin(), res.end(), 0);
	tree.resize(n);
	graph.resize(n);
	vis.resize(n, false);
	sbtree.resize(n, 1);
	for (int i = 0; i < m; i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	dfs1(0);
	int mn = min(a, min(a, b)), mnind = 0;
	if (a == mn){
		mnind = 1;
	}else if (b == mn){
		mnind = 2;
	}else{
		mnind = 3;
	}
	int ort = min(max(a, b), min(max(b, c), max(a, c))), ortind;
	if (a == ort && mnind != 1){
		ortind = 1;
	}else if (b == ort && mnind != 2){
		ortind = 2;
	}else{
		ortind = 3;
	}
	int hid = 6 - mnind - ortind;
	for (int i = 0; i < n; i++){
		if (sbtree[i] >= mn && n - sbtree[i] >= ort){
			dfs2(i, mnind, mn);
			dfs2(0, ortind, ort);
			for (int i = 0; i < n; i++){
				if (res[i] == 0)
					res[i] = hid;
			}
			break;
		}else if (sbtree[i] >= ort && n - sbtree[i] >= mn){
			dfs2(i, ortind, ort);
			dfs2(0, mnind, mn);
			for (int i = 0; i < n; i++){
				if (res[i] == 0)
					res[i] = hid;
			}
			break;
		}
	}
	return res;
}

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