Submission #1290770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290770		Sofiatpc	Split the Attractions (IOI19_split)	C++20	0 / 100	636 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 qtdb[MAXN], qtdc[MAXN], sub[MAXN], A,B,C, marc[3];

void dfsIni(int s, int p){
	sub[s] = 1; qtdb[s] = 0; qtdc[s] = 0;
	for(int viz : adj[s])
		if(viz != p){
			dfsIni(viz,s);
			sub[s] += sub[viz];
			qtdb[s] += qtdb[viz];
			qtdc[s] += qtdc[viz];
		}
	if(sub[s] == B)qtdb[s]++;
	if(sub[s] == C)qtdc[s]++;
}

void marcar(int s, int p, int x){
	res[s] = x;
	for(int viz : adj[s])
		if(viz != p && res[viz] == 0)marcar(viz,s,x);
}

int girar(int s, int p){
	for(int viz : adj[s]){
		if(sub[viz] == A && (qtdb[s]-qtdb[viz]-(sub[s] == B) > 0 || qtdc[s]-qtdc[viz]-(sub[s] == C) > 0)){
			marcar(viz,s,marc[0]);
			int cur = s, pai = -1;
			while(cur == s || (sub[cur] != B && sub[cur] != C) ){
				for(int viz : adj[cur]){
					if(viz != pai && res[viz] == 0 && (qtdb[viz] > 0 || qtdc[viz] > 0)){pai = cur; cur = viz; break;}
				}
			}
			if(sub[cur] == B){marcar(cur,pai,marc[1]); marcar(s,-1,marc[2]);}
			else {marcar(cur,pai,marc[2]); marcar(s,-1,marc[1]);}
			return viz;
		}
	}

	for(int viz : adj[s])
		if(viz != p){
			 qtdb[s] -= qtdb[viz]+(sub[s] == B); qtdc[s] -= qtdc[viz]+(sub[s] == C); sub[s] -= sub[viz];
			 sub[viz] += sub[s]; qtdb[viz] += qtdb[s]+(sub[viz]==B); qtdc[viz] += qtdc[s]+(sub[viz]==C);
			 int x = girar(viz,s);
			 if(x != -1)return x;
			 qtdb[viz] -= qtdb[s]+(sub[viz]==B); qtdc[viz] -= qtdc[s]+(sub[viz]==C); sub[viz] -= sub[s];
			 sub[s] += sub[viz]; qtdb[s] += qtdb[viz]+(sub[s] == B); qtdc[s] += qtdc[viz]+(sub[s] == C);
		}
	return -1;
}

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]);
	}

	marc[0] = 1; marc[1] = 2; marc[2] = 3; A = a; B = b; C = c;
	dfsIni(0,-1);
	int x = girar(0,-1);
	if(x != -1)return res;

	marc[0] = 2; marc[1] = 1; marc[2] = 3; A = b; B = a; C = c;
	dfsIni(0,-1);
	x = girar(0,-1);
	if(x != -1)return res;

	marc[0] = 3; marc[1] = 2; marc[2] = 1; A = c; B = b; C = a;
	dfsIni(0,-1);
	x = girar(0,-1);
	if(x != -1)return res;

	if(x == -1){
		for(int i = 0; i < n; i++)res[i] = 0;
	}
	return res;
}

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