Submission #1224890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224890		nickolasarapidis	Split the Attractions (IOI19_split)	C++17	0 / 100	36 ms	9288 KiB

split

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

const int MAXN = 100000;

vector<int> adj[MAXN];
vector<int> id(MAXN, 0);
vector<bool> visited(MAXN, false);

int cnt = 0, As, Bs, Cs;

void dfs(int s){
	if(visited[s]) return;
	visited[s];
	id[s] = 2;
	cnt++;
	for(auto u : adj[s]){
		if(cnt < Bs) dfs(u);
	}
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
	As = A; Bs = B; Cs = C;
	for(int i = 0; i < p.size(); i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	if(p.size() == N - 1){
		for(int i = 0; i < A; i++){
			id[i] = 1;
		}
		for(int i = A; i < A + B; i++){
			id[i] = 2;
		}
		for(int i = A + B; i < N; i++){
			id[i] = 3;
		}
	}
	else{
		bool a = false;
		dfs(0);
		for(int i = 0; i < N; i++){
			if(id[i] != 2){
				id[i] = 3;
				if(a != true){
					id[i] = 1;
					a = true;
				}
			}
		}
	}
	vector<int> s(N);
	for(int i = 0; i < N; i++){
		s[i] = id[i];
	}
	return s;
}

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