Submission #1222801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222801		nikd	Split the Attractions (IOI19_split)	C++20	100 / 100	96 ms	27208 KiB

split

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

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<array<int, 2>> numbers(3);
	numbers[0] = {a, 1};
	numbers[1] = {b, 2};
	numbers[2] = {c, 3};

	sort(numbers.begin(), numbers.end());
	array<int, 3> mp = {numbers[0][1], numbers[1][1], numbers[2][1]};
	a = numbers[0][0]; b = numbers[1][0]; c = numbers[2][0];
	
	vector<vector<int>> adj(n);
	int m = p.size();
	for(int i = 0; i<m; i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	vector<vector<int>> t(n);
	vector<vector<int>> back(n);
	vector<int> h(n, 0);
	vector<int> sz(n, 1);
	vector<bool> vis(n, 0);
	function<void(int)> build_tree = [&](int v){
		vis[v] = 1;
		for(int u: adj[v]){
			if(vis[u]) back[v].push_back(u);
			else{
				t[v].push_back(u);
				h[u] = h[v]+1;
				build_tree(u);
				sz[v] += sz[u];
			}
		}
		return;
	};
	build_tree(0);
	//individuo i nodi possibili
	vector<int> nodes;
	function<void(int)> find_nodes = [&](int v){
		if(sz[v] < a) return;
		bool b = 1;
		for(int u: t[v]){
			if(sz[u] >= a){
				b = 0;
				find_nodes(u);
			}
		}
		if(b) nodes.push_back(v);
		return;
	};
	find_nodes(0);

	//provo tutti i nodi fino a quando non trovo uno che funziona
	vector<bool> rem(n, 0);
	vector<int> sl(n, 0);
	for(int nd: nodes){
		int curr_sz = sz[nd];
		function<bool(int)> check_back = [&](int v) -> bool{
			for(int u: back[v]){
				if(h[u] < h[nd]) return 1;
			}
			for(int u: t[v]){
				if(check_back(u)) return 1;
			}
			return 0;
		};
		for(int u: t[nd]){
			if(curr_sz - sz[u] >= a && check_back(u)){
				curr_sz -= sz[u];
				rem[u] = 1;
			}
		}
		// n-curr_sz >= a
		if(n-curr_sz >= b){
			//ho trovato la sol :D
			//dfs dalla root per scegliere a
			for(int i = 0; i<n; i++) sl[i] = mp[2];
			int cnt = 0;
			function<bool(int)> find_a = [&](int v) -> bool{
				sl[v] = mp[0];
				if(++cnt == a) return 1;
				for(int u: t[v]){
					if(rem[u]) continue;
					if(find_a(u)) return 1;
				}
				return 0;
			};
			assert(find_a(nd));
			//dfs dalla root per scegliere b
			cnt = 0;
			vector<bool> vis2(n, 0);
			function<bool(int)> find_b = [&](int v) -> bool{
				sl[v] = mp[1];
				if(++cnt == b) return 1;
				vis2[v] = 1;
				for(int u: adj[v]){
					if(sl[u] == mp[0] || vis2[u]) continue;
					if(find_b(u)) return 1;
				}
				return 0;
			};
			assert(find_b(0));
			return sl;
 		}
		else if(curr_sz >= b && n-curr_sz >= a){
			for(int i = 0; i<n; i++) sl[i] = mp[2];
			int cnt = 0;
			function<bool(int)> find_a = [&](int v) -> bool{
				sl[v] = mp[1];
				if(++cnt == b) return 1;
				for(int u: t[v]){
					if(rem[u]) continue;
					if(find_a(u)) return 1;
				}
				return 0;
			};
			assert(find_a(nd));
			//dfs dalla root per scegliere b
			cnt = 0;
			vector<bool> vis2(n, 0);
			function<bool(int)> find_b = [&](int v) -> bool{
				sl[v] = mp[0];
				if(++cnt == a) return 1;
				vis2[v] = 1;
				for(int u: adj[v]){
					if(sl[u] == mp[1] || vis2[u]) continue;
					if(find_b(u)) return 1;
				}
				return 0;
			};
			assert(find_b(0));
			return sl;
		}
	}
	return sl;
}

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