Submission #427594

#	Time	Username	Problem	Language	Result	Execution time	Memory
427594		dreezy	Split the Attractions (IOI19_split)	C++17	11 / 100	119 ms	10400 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;
vector<bool> vis;
bool dfs(int n){
	cnt++;
	vis[n] = true;
	ans[n] = 2;
	if(cnt == b){
		return true;
	}
	for(int adj : graph[n]){
		if(vis[adj]) continue;
		if(dfs(adj))
			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, 3);
	vis.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);
	
	for(int i =0; i<n ;i++){
		if (ans[i] == 3){
			ans[i] = 1;
			break;
		}
	}
	return ans;
	
	
}


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

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