Submission #295666

#	Time	Username	Problem	Language	Result	Execution time	Memory
295666		rqi	Split the Attractions (IOI19_split)	C++14	7 / 100	84 ms	9340 KiB

split

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

typedef vector<int> vi;

#define pb push_back
#define sz(x) (int)(x).size()

const int mx = 100005;

int n;
bool SUB1 = 1;
bool SUB2 = 1;
bool SUB3 = 1;
bool SUB4 = 1;
vi adj[mx];
vi res;


bool wvisited[mx];
void wdfs(int node){
	if(wvisited[node]) return;
	wvisited[node] = 1;
	for(auto u: adj[node]){
		if(res[node] == res[u]) wdfs(u);
	}
}

bool works(int a, int b, int c){
	for(auto u: res){
		if(u == 1) a--;
		else if(u == 2) b--;
		else if(u == 3) c--;
	}
	if(a != 0 || b != 0 || c != 0) return 0;
	
	for(int j = 1; j <= 3; j++){
		for(int i = 0; i < n; i++) if(res[i] == j){
			wdfs(i);
			break;
		}
	}
	for(int i = 0; i < n; i++) if(!wvisited[i]) return 0;
	return 1;
}

vi find_split(int _n, int a, int b, int c, vi p, vi q) {
	n = _n;
	res = vi(n, 0);
	for(int i = 0; i < sz(p); i++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}

	
	
	for(int i = 0; i < n; i++){
		if(sz(adj[i]) > 2) SUB1 = 0;
	}
	if(a != 1) SUB2 = 0;
	if(sz(p) != n-1) SUB3 = 0;
	if(n > 2500 || sz(p) > 5000) SUB4 = 0;

	if(SUB1){
		int A = 0;
		int B = 0;
		int C = 0;
		int cur = 0;
		for(int i = 0; i < n; i++) if(sz(adj[i]) == 1) cur = i;

		int last = -1;

		while(true){
			if(A < a){
				res[cur] = 1;
				A++;
			}
			else if(B < b){
				res[cur] = 2;
				B++;
			}
			else if(C < c){
				res[cur] = 3;
				C++;
			}
			else break;

			if(adj[cur][0] == last){
				if(sz(adj[cur]) == 1) break;
				last = cur;
				cur = adj[cur][1];
			}
			else{
				last = cur;
				cur = adj[cur][0];
			}
		}

		return res;
	}

	if(SUB2){
		vi inComp(n, 0);
		queue<int> q;
		
		cout << b << "\n";
		int B = 0;
		inComp[0] = 1;
		B++;
		q.push(0);
		while(sz(q)){
			int node = q.front();
			q.pop();
			for(auto u: adj[node]) if(inComp[u] == 0 && B < b){
				inComp[u] = 1;
				B++;
				q.push(u);
			}
			if(B == b) break;
		}	

		for(int i = 0; i < n; i++) if(inComp[i] == 1) res[i] = 2;
		for(int i = 0; i < n; i++){
			if(inComp[i] == 0){
				res[i] = 1;
				break;
			}
		}
		for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = 3;

		return res;
	}
	assert(0 == 1);
	return res;
}

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