Submission #1290992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290992		ChuanChen	Split the Attractions (IOI19_split)	C++20	18 / 100	82 ms	16688 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(v) cerr << #v << ": " << v << "   ";
#define debugln(v) cerr << #v << ": " << v << endl;


const int MAXN = 1e5+5;

int small, large, meio;
vector<int> res, imp;
vector<int> adj[MAXN];
int pai[MAXN], sz[MAXN];
bool used1[MAXN], used2[MAXN], used3[MAXN];

void dfs_1(int no){
	used1[no] = true;
	sz[no] = 1;
	for(int v : adj[no]){
		if(used1[v]) continue;
		pai[v] = no;
		dfs_1(v);
		sz[no] += sz[v];
	}
}

void dfs_2(int no, int c){
	used2[no] = true;
	// debug(small) debugln(no);
	res[no] = c;
	for(int v : adj[no]){
		if(used2[v] || small == 0) continue;
		small--;
		dfs_2(v, c);
	}
}


void dfs_3(int no, int c){
	used3[no] = true;
	// debug(meio) debugln(no);
	res[no] = c;
	for(int v : adj[no]){
		if(used3[v] || meio == 0) continue;
		meio--;
		dfs_3(v, c);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);
	imp.resize(n, 0);
	small = min({a, b, c});
	large = max({a, b, c}); //vai ser galera soltos
	meio = n-small-large; //vai ser o que der

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

	// cerr << "i sz  pai\n";
	vector<pair<int, int>> aux;
	for(int i = 0; i < n; i++){
		// cerr << i << "  " << sz[i] << "  " << pai[i] << "\n";
		aux.push_back({sz[i], i});
	}
	sort(aux.begin(), aux.end());
	int sm = lower_bound(aux.begin(), aux.end(), make_pair(small, 0))->second;
	int can2= lower_bound(aux.begin(), aux.end(), make_pair(meio, 0))->second;
	if(sz[sm]-small > sz[can2]-meio){
		sm = can2;
		if(n-sz[sm] < small) return imp;
	}
	else{
		if(n-sz[sm] < meio) return imp;
	}

	// debugln(sm);
	// debugln(pai[sm]);
	int cor3 = 6;
	used2[pai[sm]] = true;
	small--;
	if(small+1 == a){
		dfs_2(sm, 1);
		cor3--;
		a = 0;
	}
	else if(small+1 == b){
		dfs_2(sm, 2);
		cor3-=2;
		b = 0;
	}
	else{
		dfs_2(sm, 3);
		cor3-=3;
		c = 0;
	}
	// debugln(cor3);

	used3[sm] = true;
	meio--;
	if(a != 0 && meio+1 == a){
		dfs_3(pai[sm], 1);
		cor3--;
	}
	else if(b != 0 && meio+1 == b){
		dfs_3(pai[sm], 2);
		cor3-=2;
	}
	else{
		dfs_3(pai[sm], 3);
		cor3-=3;
	}
	// debugln(cor3);
	for(int &i : res) if(i == 0) i = cor3;
	return res;
}

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