Submission #427583

#	Time	Username	Problem	Language	Result	Execution time	Memory
427583		dreezy	Split the Attractions (IOI19_split)	C++17	0 / 100	112 ms	13980 KiB

split

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

const int maxn = 1e5 + 5;
vector<int> graph[maxn];
int a, b, c;
//assume a is smallest
//assume b is second smallest

vector<int> ans;
int cnt = 0;
bool dfs(int n, int p){
	cnt++;
	ans[n] = 2;
	if(cnt == b){
		return true;
	}
	for(int adj : graph[n]){
		if(adj == p) continue;
		if(dfs(adj, n))
			return true;
	}
	
	
	return cnt == b;
}



vector<int> find_split(int n, int a_, int b_, int c_, vector<int> p, vector<int> q) {
	
	
	a = a_;
	b = b_;
	c = c_;
	int m = p.size();
	ans.assign(n, 0);

	for(int i =0; i<m ;i++){
		//cout << p[i] <<", "<<q[i]<<endl; 
		graph[p[i]].pb(q[i]);
		graph[q[i]].pb(p[i]);
	}
	
	if(b)
		dfs(0, -1);
	
	int cntc = 0;
	for(int i =0; i<n ;i++){
		if(ans[i] == 0 and cntc < c){
			cntc++;
			ans[i] = 3;
		}
		else if (ans[i] == 0){
			ans[i] = 1;
			break;
		}
	}
	return ans;
	
	
}


/************/

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