Submission #1210490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210490		bangan	Split the Attractions (IOI19_split)	C++20	18 / 100	52 ms	15304 KiB

split

#include "split.h"
using namespace std;

#define X first 
#define Y second
#define pair pair<int, int>

#define pb push_back
#define all(a) a.begin(), a.end()

const int N = 2e5 + 4;

vector<int> adj[N];
vector<vector<int>> V;
bool vis[N];

void dfs(int v) {
	vis[v]=1;
	V.back().pb(v);
	for (int u : adj[v]) if (!vis[u]) dfs(u);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i=0; i<p.size(); i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	for (int i=0; i<n; i++) if (!vis[i]) {
		V.pb({});
		dfs(i);
	}
	vector<pair> ord{{a,1}, {b,2}, {c,3}};
	sort(all(ord), [&](auto lhs, auto rhs) {
		return lhs.X > rhs.X;
	});
	sort(all(V), [&](auto &x, auto &y) {
		return x.size()<y.size();
	});
	vector<int> ans(n);
	int rep=2;
	while (rep--) {
		for (auto &vec : V) if (vec.size() >= ord.back().X) {
			int t = ord.back().X;
			while (t--) {
				int v = vec.back();
				ans[v] = ord.back().Y;
				vec.pop_back();
			}
			ord.pop_back();
			break;
		}
	}
	if (ord.size()>1) return vector(n, 0);
	for (int i=0; i<n; i++) if (!ans[i]) ans[i] = ord.back().Y;
	return ans;
}

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