Submission #443314

#	Time	Username	Problem	Language	Result	Execution time	Memory
443314		vanic	Split the Attractions (IOI19_split)	C++14	18 / 100	122 ms	13984 KiB

split

#include "split.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

const int maxn=2e5+5;

int vel[3];
int ind[3];
vector < int > ms[maxn];
int n, m;

bool cmp(int a, int b){
	return vel[a]<vel[b];
}

bool cmp1(int a, int b){
	return ms[a].size()<ms[b].size();
}

vector < int > col;
int treba;
int svi[maxn];
int koja, zamj;
int tren;

void dfs(int x){
	if(!vel[ind[tren]]){
		tren++;
	}
	col[x]=ind[tren]+1;
	vel[ind[tren]]--;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!col[ms[x][i]]){
			dfs(ms[x][i]);
		}
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n=N;
	col.resize(n, 0);
	m=p.size();
	vel[0]=a;
	vel[1]=b;
	vel[2]=c;
	for(int i=0; i<3; i++){
		ind[i]=i;
	}
	sort(ind, ind+3, cmp);
	for(int i=0; i<m; i++){
		ms[p[i]].push_back(q[i]);
		ms[q[i]].push_back(p[i]);
	}
	for(int i=0; i<n; i++){
		svi[i]=i;
	}
	sort(svi, svi+n, cmp1);
	dfs(svi[0]);
	return col;
}

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