Submission #154328

#	Time	Username	Problem	Language	Result	Execution time	Memory
154328		asifthegreat	Split the Attractions (IOI19_split)	C++14	0 / 100	16 ms	15608 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;

#define pii pair<int,int>

const int N = 300000;
vector<int>graph[N],tree[N];
map<char,int>mp;

vector<pii>vcase1;
map<pii,bool>block;
int n;
int mark[N],subtree[N];
int vis[N];
int baki;
int attheke,itheke,ijabe,atjabe;


void make_it_tree(int at){
	vis[at] = true;
	for(auto i: graph[at]){
		if(vis[i])continue;
		tree[at].push_back(i);
		tree[i].push_back(at);
		make_it_tree(i);
	}
}
void subtree_count(int at,int par){
	subtree[at] = 1;
	for(auto i: tree[at]){
		if(i == par)continue;
		subtree_count(i,at);
		subtree[at] += subtree[i];
	}
}
void case1(int at,int par,int a){
	if(!vcase1.empty())return;
	for(auto i: tree[at]){
		if(i == par)continue;
		// printf("edge %d---%d and sizes are (%d,%d) where a = %d\n",at,i,n-subtree[i],subtree[i],a);
		if(subtree[i] > a and n-subtree[i] > a){
			vcase1.push_back({at,i});
			return;
		}
		case1(i,at,a);
	}
}
void case01(int at){
	if(atjabe == 0)return;
	atjabe--;
	vis[at] = true;
	mark[at] = attheke;
	for(auto i: tree[at]){
		if(vis[i] or block[{at,i}])continue;
		case01(i);
	}
}
void case11(int at){
	if(ijabe == 0)return;
	ijabe--;
	vis[at] = true;
	mark[at] = itheke;
	for(auto i: tree[at]){
		if(vis[i] or block[{at,i}])continue;
		case11(i);
	}
}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
	
	vector<int>tempabc;
	tempabc.push_back(a);
	tempabc.push_back(b);
	tempabc.push_back(c);
	sort(tempabc.begin(),tempabc.end());
	for(int i = 0; i < (int)tempabc.size();i++){
		if(tempabc[i] == a){
			mp['a'] = i+1;
			tempabc[i] = 1000000000;
			break;
		}
	}
	for(int i = 0; i < (int)tempabc.size();i++){
		if(tempabc[i] == b){
			mp['b'] = i+1;
			tempabc[i] = 1000000000;
			break;
		}
	}
	for(int i = 0; i < (int)tempabc.size();i++){
		if(tempabc[i] == c){
			mp['c'] = i+1;
			tempabc[i] = 1000000000;
			break;
		}
	}

	n = nn;
	vector<int> res;
	for(int i = 0; i < (int)p.size();i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	make_it_tree(0);

	subtree_count(0,-1);
	// for(int i = 0; i < n;i++){
	// 	printf("%d = %d\n",i,subtree[i]);
	// }
	case1(0,-1,min(a,min(b,c)));
	// cout << "kere mama ke khobor\n";
	if(!vcase1.empty()){
		block[{vcase1[0].first,vcase1[0].second}] = true;
		if(subtree[vcase1[0].second] >= n-subtree[vcase1[0].second]){
			// it means child's subtree is greater 
			itheke = 2;
			ijabe = b;
			attheke = 1; 
			atjabe = a;
		}
		else {
			// it means parent's subtree is greater 
			itheke = 1;
			ijabe = a;
			attheke = 2; 
			atjabe = b;
		}
		memset(vis,false,sizeof vis);
		case01(vcase1[0].first);
		case11(vcase1[0].second);
		for(int i = 0; i < n;i++){
			if(!mark[i])mark[i] = 3;
		}
		for(int i = 0; i < n;i++){
			if(mark[i] == 1)res.push_back(mp['a']);
			if(mark[i] == 2)res.push_back(mp['b']);
			if(mark[i] == 3)res.push_back(mp['c']);
		}
		return res;
	}
	// case 1 completed. There is another fucking case and I have to write more than 100 lines for case 2
	// how fucckig amazing -_- 
	for(int i = 0; i < n;i++)res.push_back(0);
	return res;
}

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