Submission #569409

#	Time	Username	Problem	Language	Result	Execution time	Memory
569409		ngpin04	Split the Attractions (IOI19_split)	C++17	40 / 100	171 ms	23304 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];
vector <int> g[N];

int ans[N];
int sz[N];
int n,m,a,b,c,par,ok = -1;

int ca = 1, cb = 2, cc = 3;

bool vis[N];

void dfs(int u) {
	sz[u] = 1;
	vis[u] = true;
	for (int v : adj[u]) if (!vis[v]) {
		g[v].push_back(u);
		g[u].push_back(v);
		dfs(v);
		sz[u] += sz[v];
		if (sz[v] >= a && (n - sz[v]) >= b) {
			ok = v;
			par = u;
		}

		if (sz[v] >= b && (n - sz[v]) >= a) {
			ok = u;
			par = v;
		}
	}
}

void paint(int u, int &a, int ca, int p) {
	a--;
	ans[u] = ca;

	for (int v : g[u]) if (v != p) {
		if (a == 0)
			break;
		paint(v, a, ca, u);
	}
}

vector<int> find_split(int _n, int _a, int _b, int _c, 
	vector<int> p, vector<int> q) { 
	m = p.size();
	n = _n;
	a = _a;
	b = _b;
	c = _c;
	if (a > b) {
		swap(a, b);
		swap(ca, cb);
	}

	if (a > c) {
		swap(a, c);
		swap(ca, cc);
	}

	if (b > c) {
		swap(b, c);
		swap(cb, cc);
	}
	
	for (int i = 0; i < m; i++) {
		auto [u, v] = tuple <int, int> {p[i], q[i]};
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(0);
	if (ok != -1) {
		paint(ok, a, ca, par);
		paint(par, b, cb, ok);
		vector <int> res;
		for (int i = 0; i < n; i++) {
			if (ans[i] == 0)
				ans[i] = cc;
			res.push_back(ans[i]);
		}
		return res;
	}
	return vector <int> (n, 0);
}

//#include "grader.cpp"

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