Submission #810386

#	Time	Username	Problem	Language	Result	Execution time	Memory
810386		Sohsoh84	Split the Attractions (IOI19_split)	C++17	40 / 100	658 ms	30508 KiB

split

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

using namespace std;

typedef pair<int, int> pll;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define X		first
#define Y		second
#define all(x)		(x).begin(), (x).end()

const int MAXN = 2e5 + 10;

vector<int> adjt[MAXN], adj[MAXN];
int a, b, c, n, m, ans[MAXN], sz[MAXN], T[4] = {0, 1, 2, 3};
bool flag = false;
bool vis[MAXN];

void dfs_ans(int v, int p, int c, int& cnt) {
	if (cnt) {
		ans[v] = c;
		cnt--;
	}

	for (int u : adj[v]) {
		if (u == p) continue;
		dfs_ans(u, v, c, cnt);
	}
}

void dfs_tree(int v) {
	vis[v] = true;
	for (int u : adjt[v])
		if (!vis[u])
			dfs_tree(u), adj[v].push_back(u), adj[u].push_back(v);
}

void dfs1(int v, int p) {
	sz[v] = 1;
	for (int u : adj[v]) {
		if (u == p) continue;

		dfs1(u, v);
		sz[v] += sz[u];

		if (!flag && sz[u] >= a && n - sz[u] >= b) {
			flag = true;
			dfs_ans(u, v, 1, a);
			dfs_ans(v, u, 2, b);
		}

		if (!flag && sz[u] >= b && n - sz[u] >= a) {
			flag = true;
			dfs_ans(u, v, 2, b);
			dfs_ans(v, u, 1, a);
		}
	}
}

namespace DSU {
	int par[MAXN];

	inline void init() {
		for (int i = 1; i <= n; i++)
			par[i] = i;
	}

	int find(int v) {
		return par[v] == v ? v : par[v] = find(par[v]);
	}

	inline bool unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return false;
		par[v] = u;
		
		return true;
	}
}

vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p_, vector<int> q_) {
	n = n_, a = a_, b = b_, c = c_;
	if (b > c) swap(b, c), swap(T[2], T[3]);
	if (a > c) swap(a, c), swap(T[1], T[3]);
	if (a > b) swap(a, b), swap(T[1], T[2]);
	
	m = p_.size();	

	vector<pll> edges;

	for (int i = 0; i < m; i++) {
		int u = p_[i], v = q_[i];
		u++, v++;
		adjt[u].push_back(v);
		adjt[v].push_back(u);
	}	


	int t = 100;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	while (t-- && !flag) {	
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			adj[i].clear(), vis[i] = false;
		
		dfs_tree(v);
		dfs1(1, 0);
	}

	if (*max_element(ans + 1, ans + n + 1) > 0) {
		for (int i = 1; i <= n; i++)
			if (ans[i] == 0)
				ans[i] = 3;

	}

	vector<int> res;
	for (int i = 1; i <= n; i++)
		res.push_back(T[ans[i]]);

	return res;
}

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