Submission #1290811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290811		Sofiatpc	Split the Attractions (IOI19_split)	C++20	0 / 100	602 ms	1114112 KiB

split

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

using namespace std;

const int MAXN = 1e5+5;
vector<int> adj[MAXN], res;
int sub[MAXN], val[4];

void dfs(int s, int p, int x){
	if(val[x] == 0)return;
	val[x]--; res[s] = x;
	for(int viz : adj[s])
		if(viz != p)dfs(viz,s,x);
}

int dfsIni(int s, int p){
	sub[s] = 1;
	for(int i = 0; i < adj[s].size(); i++)
		if(adj[s][i] != p){
			int x = dfsIni(adj[s][i],s);
			if(x)return 1;
			sub[s] += sub[adj[s][i]];
		}

	for(int i = 1; i <= 3; i++)
		if(val[i] == sub[i]){
			dfs(s,p,i); val[i] = 0;
			int nxt = i+1; if(nxt == 4)nxt = 1;
			dfs(p,s,nxt);
			return 1;
		}
	return 0;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);

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

	val[1] = a; val[2] = b; val[3] = c;
	int x = dfsIni(0,-1);
	if(x != 0){
		for(int i = 0; i < n; i++)
			if(res[i] == 0){
				for(int j = 1; j <= 3; j++)
					if(val[j] > 0){res[i] = j; val[j]--;}
			}
	}



	return res;
}

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