Submission #428310

#	Time	Username	Problem	Language	Result	Execution time	Memory
428310		Hazem	Split the Attractions (IOI19_split)	C++14	18 / 100	102 ms	13656 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

vector<int>adj[N],ans;
int n,m;
bool vis[N];

void dfs(int i,int c,int &cnt){

	if(vis[i]||cnt<=0)
		return ;
	
	cnt--;
	vis[i] = 1;ans[i] = c;
	for(auto x:adj[i])
		if(!vis[x])dfs(x,c,cnt);
}

vector<int> find_split(int n1, int a, int b, int c, vector<int> p, vector<int> q) {

	n = n1;m = p.size();
	ans = vector<int>(n,0);

	for(int i=0;i<m;i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	int st = 0;
	for(int i=0;i<n;i++)
		if(adj[i].size()==1)
			st = i;
	
	dfs(st,1,a);
	for(int i=0;i<n;i++)
		if(!vis[i]){
			dfs(i,2,b);
			break;
		}

	for(int i=0;i<n;i++)
		if(!ans[i])ans[i] = 3;
	
	return ans;
}

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