Submission #289648

#	Time	Username	Problem	Language	Result	Execution time	Memory
289648		ChrisT	Split the Attractions (IOI19_split)	C++17	22 / 100	726 ms	1048580 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MN = 1e5 + 5;
vector<int> adj[MN];
bool vis[MN];
vector<int> subtask1 (int n, int a, int b, int c) {
	vector<int> ret(n);
	int cur = 1, lst = -1;
	for (int i = 0; i < n; i++) {
		ret[cur-1] = (i < a ? 1 : (i < a+b ? 2 : 3));
		for (int j : adj[cur]) if (j != lst) {
			lst = cur; cur = j; break;
		}
	}
	return ret;
}
vector<int> subtask2 (int n, int a, int b, int c) {
	vector<int> ret(n,3);
	int leaf = -1;
	function<void(int)> dfs = [&] (int cur) {
		bool isLeaf = 1; vis[cur] = 1;
		for (int i : adj[cur]) if (!vis[i]) {
			dfs(i); isLeaf = 0;
		} 
		if (isLeaf) leaf = cur;
	};
	dfs(1);
	assert(~leaf && leaf != 1);
	ret[leaf-1] = 1;
	queue<int> q; q.push(1); memset(vis,0,sizeof vis);
	vis[1] = vis[leaf] = 1;
	for (int i = 0; i < b; i++) {
		int cur = q.front(); q.pop();
		ret[cur-1] = 2;
		for (int i : adj[cur]) if (!vis[i]) {
			vis[i] = 1;
			q.push(i);
		}
	}
	return ret;
}
vector<int> subtask3 (int n, int a, int b, int c) {
	vector<int> ret(n),sz(n+1),wot(4),par(n+1);
	wot[1] = 1; wot[2] = 2; wot[3] = 3;
	if (a >= b && a > c) swap(wot[1],wot[3]), swap(a,c);
	else if (b >= a && b > c) swap(wot[2],wot[3]), swap(b,c);  
	function<void(int,int)> dfs = [&] (int cur, int p) {
		sz[cur] = 1; par[cur] = p;
		for (int i : adj[cur]) if (i != p) {
			dfs(i,cur);
			sz[cur] += sz[i];
		}
	};
	auto bfs = [&] (int st, int dont, int num, int val) {
		 memset(vis,0,sizeof vis);
		 queue<int> q; q.push(st); vis[st] = vis[dont] = 1;
		 for (int i = 0; i < num; i++) {
			 int cur = q.front(); q.pop();
			 ret[cur-1] = val;
			 for (int j : adj[cur]) if (!vis[j]) {
				 vis[j] = 1;
				 q.push(j);
			 }
		 }
	};
	dfs(1,-1);
	for (int i = 1; i <= n; i++) {
		if (sz[i] >= a && n - sz[i] >= b) {
			fill(ret.begin(),ret.end(),wot[3]);
			bfs(i,par[i],a,wot[1]); 
			bfs(1,i,b,wot[2]);
			return ret;
		}
		if (sz[i] >= b && n - sz[i] >= a) {
			fill(ret.begin(),ret.end(),wot[3]);
			bfs(i,par[i],b,wot[2]);
			bfs(1,i,a,wot[1]);
			return ret;
		}
	}
	return ret;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> deg(n); int mxDeg = 0;
	for (int i = 0; i < (int)p.size(); i++) {
		mxDeg = max(mxDeg,++deg[p[i]]);
		mxDeg = max(mxDeg,++deg[q[i]]);
		adj[++p[i]].push_back(++q[i]);
		adj[q[i]].push_back(p[i]);
	}
	if (mxDeg <= 2) return subtask1(n,a,b,c);
	else if (a == 1) return subtask2(n,a,b,c);
	return subtask3(n,a,b,c);
}

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