Submission #583690

#	Time	Username	Problem	Language	Result	Execution time	Memory
583690		joelau	Split the Attractions (IOI19_split)	C++14	0 / 100	1002 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,A,B,C, dist[100005];
vector<int> lst[100005], ans;
pair<int,int> tmp[3];
queue<int> Q;

void dfs (int x, int p, int d) {
	dist[x] = d;
	for (int v: lst[x]) if (v != p) dfs(v,x,d+1);
}

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;
	for (int i = 0; i < M; ++i) lst[p[i]].push_back(q[i]), lst[q[i]].push_back(p[i]);
	dfs(0,-1,0);
	pair<int,int> S = make_pair(-1,-1);
	for (int i = 0; i < N; ++i) S = max(S,make_pair(dist[i],i));
	dfs(S.second,-1,0);
	pair<int,int> T = make_pair(-1,-1);
	for (int i = 0; i < N; ++i) T = max(T,make_pair(dist[i],i));
	tmp[0] = make_pair(A,1), tmp[1] = make_pair(B,2), tmp[2] = make_pair(C,3);
	sort(tmp,tmp+3);
	ans.assign(N,tmp[2].second);
	Q.push(S.second);
	ans[S.second] = tmp[0].second;
	int cnt = 1;
	while (!Q.empty() && cnt < tmp[0].first) {
		int u = Q.front(); Q.pop();
		for (int v: lst[u]) if (ans[v] == tmp[2].second) {
			ans[v] = tmp[0].second, cnt++;
			Q.push(v);
			if (cnt >= tmp[0].first) break;
		}
	}
	while (!Q.empty()) Q.pop();
	if (cnt < tmp[0].first || ans[T.second] == tmp[0].second) return vector<int>(N,0);
	Q.push(T.second);
	ans[T.second] = tmp[1].second;
	cnt = 1;
	while (!Q.empty() && cnt < tmp[1].first) {
		int u = Q.front(); Q.pop();
		for (int v: lst[u]) if (ans[v] == tmp[2].second) {
			ans[v] = tmp[1].second, cnt++;
			Q.push(v);
			if (cnt >= tmp[1].first) break;
		}
	}
	if (cnt < tmp[1].first) return vector<int>(N,0);
	return ans;
}

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