Submission #292497

#	Time	Username	Problem	Language	Result	Execution time	Memory
292497		miss_robot	Split the Attractions (IOI19_split)	C++14	40 / 100	120 ms	15608 KiB

split

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

#pragma GCC optimize("O3")

using namespace std;

const int N = 1e5;
int n, A, B, C, ia, ib, ic, d;
int st[N];
vector<int> g[N], sol;

void flood1(int u, int &c, int f){
	if(sol[u] || !c) return;
	sol[u] = f, c--;
	for(int v : g[u]) flood1(v, c, f);
}

void st1(){
	flood1(0, A, ia);
	for(int i = 0; i < n; i++){
		if(!sol[i]){
			flood1(i, B, ib);
			break;
		}
	}
	for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
}

void st2(){
	flood1(0, B, ib);
	for(int i = 0; i < n; i++){
		if(sol[i]) continue;
		if(A) sol[i] = ia, A--;
		else sol[i] = ic;
	}
}

void flood2(int u, int p, int &c, int f){
	if(!c) return;
	sol[u] = f, c--;
	for(int v : g[u]) if(v != p) flood2(v, u, c, f);
}

void dfs(int u, int p){
	st[u] = 1;
	for(int v : g[u]){
		if(v == p) continue;
		dfs(v, u);
		if(d) return;
		st[u] += st[v];
	}
	if(n-st[u] >= A && st[u] >= B){
		flood2(u, p, B, ib);
		flood2(p, u, A, ia);
		for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
		d = 1;
	}
	else if(st[u] >= A && n-st[u] >= B){
		flood2(u, p, A, ia);
		flood2(p, u, B, ib);
		for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic;
		d = 1;
	}
}

void st3(){
	dfs(0, 0);
}

void tmp(int tn){
	n = tn;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	int m = p.size();
	for(int i = 0, u, v; i < m; i++){
		u = p[i], v = q[i];
		g[u].push_back(v);
		g[v].push_back(u);
	}
	A = a, B = b, C = c, ia = 1, ib = 2, ic = 3;
	if(C < B) swap(B, C), swap(ib, ic);
	if(B < A) swap(A, B), swap(ia, ib);
	if(C < B) swap(B, C), swap(ib, ic);
	sol.resize(n);
	tmp(n);
	if(m == n-1) st3();
	else if(A == 1) st2();
	else st1();
	return sol;
}

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