Submission #156499

#	Time	Username	Problem	Language	Result	Execution time	Memory
156499		MoNsTeR_CuBe	Split the Attractions (IOI19_split)	C++17	11 / 100	115 ms	12636 KiB

split

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

vector< int > colouring;

vector< bool > visited;

int remaining;

void dfs(int node){
	visited[node] = true;
	
	if(remaining){
		remaining--;
		 colouring[node] = 2;
	}
	
	for(int a : Graph[node]){
		if(visited[a]) continue;
		dfs(a);
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	
	Graph.resize(N);
	colouring.resize(N);
	visited.assign(N, false);
	
	remaining = b;
		
	for(int i = 0; i < (int)p.size(); i++){
		Graph[p[i]].push_back(q[i]);
		Graph[q[i]].push_back(p[i]);
	}
	
	dfs(0);
	
	for(int i = 0; i < N; i++){
		if(colouring[i] == 2) continue;
		if(a){
			a--;
			colouring[i] = 1;
		} 
		else colouring[i] = 3;
	}
	
	return colouring;
}

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