Submission #426905

#	Time	Username	Problem	Language	Result	Execution time	Memory
426905		dreezy	Split the Attractions (IOI19_split)	C++17	7 / 100	75 ms	7924 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
/*
subtask 1, line
easy, split by sections
*/

/*
subtask 2
*/
const int maxn = 1e5 + 5;
vector<int> graph[maxn];
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> ans(n);
	int m = p.size();
	int cur = -1;
	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]);
	}
	
	for(int i =0; i<n; i++){
		if(graph[i].size() == 1)
		{
			cur = i;
			break;
		}
	}
	if(cur == -1)
		cur = 0;
	
	vector<bool> vis(n);
	while(c > 0){
		//cout <<cur<<endl;
		if(a > 0){
			a--;
			ans[cur] = 1;
		}else if(b > 0){
			b--;
			ans[cur] = 2;
		}
		else{
			c--;
			ans[cur] = 3;
		}
		vis[cur] =true;
		for(int adj : graph[cur])
		{
			if(!vis[adj])
			{
				cur = adj;
				break;
			}
		}
	}
	return ans;
	
	
}


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

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