Submission #1152724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152724		the_coding_pooh	Split the Attractions (IOI19_split)	C++20	40 / 100	1038 ms	17860 KiB

split

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

using namespace std;

#define uwu return

#define fs first
#define sc second

#define all(x) x.begin(), x.end()

mt19937 rng(time(0));

const int SIZE = 1e5 + 5;

vector <int> graph[SIZE];

bitset <SIZE> been;

vector <int> dfs_tree;

bool flag = 0;

int dfs(int n, int a, int b, int nd){
	int ret = 1;
	been[nd] = 1;
	dfs_tree.push_back(nd);
	// cerr << nd << '\n';
	for (auto i : graph[nd]){
		if(!been[i]){
			int tmp = dfs(n, a, b, i);
			if(tmp >= a && n - tmp >= b)
				flag = 1;
			if(tmp >= b && n - tmp >= a)
				flag = 1;
			ret += tmp;
		}
	}
	dfs_tree.push_back(nd);
	uwu ret;
}

int u, v;

int find_ans(int n, int a, int b, int nd){
	int ret = 1;
	been[nd] = 1;
	for (auto i : graph[nd]){
		if(!been[i]){
			int tmp = find_ans(n, a, b, i);
			if(tmp == -1)
				return -1;
			if (tmp >= a && n - tmp >= b){
				v = i;
				u = nd;
				flag = 0;
				return -1;
			}
			if(tmp >= b && n - tmp >= a){
				v = i;
				u = nd;
				flag = 1;
				return -1;
			}
			ret += tmp;
		}
	}
	uwu ret;
}

const float TIME_LIMIT = 1;

vector <int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = q.size();
	for (int i = 0; i < m; i++){
		graph[q[i]].push_back(p[i]);
		graph[p[i]].push_back(q[i]);
	}
	vector <pair<int, int>> order = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(order));
	auto ck = clock();
	int rt = 0;
	for (; (clock() - ck) / CLOCKS_PER_SEC < TIME_LIMIT;){
		for (int i = 0; i < n; i++){
			shuffle(all(graph[i]), rng);
		}
		rt = rng() % n;
		been.reset();
		dfs_tree.clear();
		dfs(n, order[0].fs, order[1].fs, rt);
		if(flag)
			break;
	}
	// cerr << "hi\n";
	if (!flag)
		uwu vector<int>(n, 0);
	been.reset();
	find_ans(n, order[0].fs, order[1].fs, rt);
	vector <int> splitted_tree[2];
	int nw = 0;
	for (int i = 0; i < (int)dfs_tree.size(); i++){
		if(dfs_tree[i] == v && !nw){
			nw = nw ^ 1;
			splitted_tree[nw].push_back(dfs_tree[i]);
		}
		else if(dfs_tree[i] == v && nw){
			splitted_tree[nw].push_back(dfs_tree[i]);
			nw = nw ^ 1;
		}
		else{
			splitted_tree[nw].push_back(dfs_tree[i]);
		}
	}
	vector <int> ret(n);
	if(!flag)
		swap(splitted_tree[0], splitted_tree[1]);
	int ptr = 0;
	// for(auto i:dfs_tree){
	// 	cerr << i << ' ';
	// }
	// cerr << '\n';
	for (auto i : splitted_tree[0]){
		// cerr << i << ' ';
		if(ptr >= order[0].fs)
			continue;;
		if (!ret[i]){
			ret[i] = order[0].sc;
			ptr++;
		}
	}
	// cerr << '\n';
	ptr = 0;
	for (auto i : splitted_tree[1]){
		// cerr << i << ' ';
		if(ptr >= order[1].fs)
			continue;;
		if (!ret[i]){
			ret[i] = order[1].sc;
			ptr++;
		}
	}
	// cerr << '\n';
	for (auto &i : ret){
		if(!i)
			i = order[2].sc;
	}
	uwu ret;
}

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