Submission #810485

#	Time	Username	Problem	Language	Result	Execution time	Memory
810485		NothingXD	Split the Attractions (IOI19_split)	C++17	18 / 100	2072 ms	26572 KiB

split

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail> 
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, m, a, b, c, A, B, C, sz[maxn], r1 = -1, r2 = -1, ans[maxn];
vector<int> g[maxn], t[maxn];
bool vis[maxn];


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs(int v){
	shuffle(all(g[v]), rng);
	vector<int> save;
	vis[v] = true;
	for (auto u: g[v]){
		if (!vis[u]){
			t[u].push_back(v);
			t[v].push_back(u);
			int idk = rng() % 2;
			if (idk) dfs(u);
			else{
				save.push_back(u);
				vis[u] = true;
			}
		}
	}
	//if (save.empty()) return;
	shuffle(all(save), rng);
	for (auto u: save){
		dfs(u);
	}
}

void bfs(int v){
	queue<int> q;
	q.push(v);
	vis[v] = true;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for (auto u: g[v]){
			if (!vis[u]){
				vis[u] = true;
				t[u].push_back(v);
				t[v].push_back(u);
				q.push(u);
			}
		}
	}
}

void find(int v, int p = -1){
	sz[v] = 1;
	for (auto u: t[v]){
		if (u != p){
			find(u, v);
			sz[v] += sz[u];
		}
	}
	if (min(n-sz[v], sz[v]) >= a){
		r1 = v;
		r2 = p;
	}
}

int solve(int v, int p, int cnt, int val){
	if (cnt == 0) return 0;
	ans[v] = val;
	cnt--;
	for (auto u: t[v]){
		if (u != p){
			cnt = solve(u, v, cnt, val);
		}
	}
	return cnt;
}


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;
	A = 1, B = 2, C = 3;
	if (a > b){
		swap(a, b);
		swap(A, B);
	}
	if (b > c){
		swap(b, c);
		swap(B, C);
	}
	if (a > b){
		swap(a, b);
		swap(A, B);
	}
	for (int i = 0; i < m; i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	for (int i = 0; i < 2*n; i++){
		memset(vis, false, sizeof vis);
		for (int j = 0; j < n; j++) t[j].clear();
		int r = rng() % n;
		dfs(r);
		find(r);
		if (r1 == -1) continue;
		vector<int> res(n, C);
		if (sz[r1] >= b) swap(r1, r2);
		solve(r1, r2, a, A);
		solve(r2, r1, b, B);
		for (int i = 0; i < n; i++){
			if (ans[i] != 0) res[i] = ans[i];
		}
		return res;
	}
	vector<int> res(n, 0);
	return res;
}

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