Submission #583695

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

split

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

int N,M,A,B,C, dist1[100005], dist2[100005];
vector<int> lst[100005], ans;
pair<int,int> tmp[3];
priority_queue< pair<int,int> > pq;

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

void dfs2 (int x, int p, int d) {
	dist2[x] = d;
	for (int v: lst[x]) if (v != p) dfs2(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]);
	dfs1(0,-1,0);
	pair<int,int> S = make_pair(-1,-1);
	for (int i = 0; i < N; ++i) S = max(S,make_pair(dist1[i],i));
	dfs1(S.second,-1,0);
	pair<int,int> T = make_pair(-1,-1);
	for (int i = 0; i < N; ++i) T = max(T,make_pair(dist1[i],i));
	dfs2(T.second,-1,0);
	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);
	pq.emplace(dist2[S.second],S.second);
	int cnt = 0;
	while (!pq.empty() && cnt < tmp[0].first) {
		int u = pq.top().second; pq.pop();
		ans[u] = tmp[0].second;
		if (++cnt >= tmp[0].first) break;
		for (int v: lst[u]) if (ans[v] == tmp[2].second) pq.emplace(dist2[v],v);
	}
	if (cnt < tmp[0].first || ans[T.second] == tmp[0].second) return vector<int>(N,0);
	while (!pq.empty()) pq.pop();
	pq.emplace(dist1[T.second],T.second);
	cnt = 0;
	while (!pq.empty() && cnt < tmp[1].first) {
		int u = pq.top().second; pq.pop();
		ans[u] = tmp[1].second;
		if (++cnt >= tmp[1].first) break;
		for (int v: lst[u]) if (ans[v] == tmp[2].second) pq.emplace(dist1[v],v);
	}
	if (cnt < tmp[1].first) return vector<int>(N,0);
	else return ans;
}

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