Submission #287816

#	Time	Username	Problem	Language	Result	Execution time	Memory
287816		user202729	Split the Attractions (IOI19_split)	C++17	0 / 100	2 ms	512 KiB

split

// moreflags=grader.cpp
// not my solution. :(
#include "split.h"
#include<array>
#if not LOCAL
#define NDEBUG
#endif
#include<algorithm>
#include<cassert>

struct Dsu{
	std::vector<int> data; // data = parent if positive, -subtreeSize if negative
	Dsu(int number){reset(number);}
	void reset(int number){
		data.assign(number, -1);
	}
	int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
	bool join(int first, int sec){
		first=root(first); sec=root(sec);
		if(first==sec) return false;
		data[sec]+=data[first];
		data[first]=sec;
		return true;
	}
};

std::vector<std::vector<int>> add;

int work(int node, int par){
	int subtreeSize=1;
	int maxChild=0;
	for(auto child: add[node]) if(child!=par){
		int const tmp=work(child, node);
		maxChild=std::max(maxChild, tmp);
		subtreeSize+=tmp;
	}
	if(std::max((int)add.size()-subtreeSize, maxChild)*2<=(int)add.size())
		throw node;
	return subtreeSize;
}

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
	add.clear(); add.resize(n);
	std::array<std::pair<int, int>, 3> sizes{{{a, 1}, {b, 2}, {c, 3}}};
	std::sort(begin(sizes), end(sizes));
	a=b=c=-1;

	Dsu dsu(n);
	for(int index=0; index<(int)p.size(); ++index){
		auto const first=p[index], sec=q[index];
		if(dsu.join(first, sec)){
			add[first].push_back(sec); add[sec].push_back(first);
		}
	}

	try{
		work(0, -1);
	}catch(int centroid){
		dsu.reset(n);

		auto const process=[&](int root)->std::vector<int>{
			assert(dsu.data[root]<0 and -dsu.data[root]>=sizes[0].first);
			assert(std::is_sorted(begin(sizes), end(sizes)));

			std::vector<int> result(n, sizes[2].second);

			for(auto& it: add) it.clear();
			for(int index=0; index<(int)p.size(); ++index){
				auto const first=p[index], sec=q[index];
				add[first].push_back(sec); add[sec].push_back(first);
			}

			auto const process=[&](std::pair<int, int> const item, int const startNode, auto condition){
				auto const [size, componentId]=item;
				std::vector<int> queue;
				queue.push_back(startNode);
				assert(result[startNode]!=componentId); result[startNode]=componentId;
				assert(condition(startNode));
				for(int start=0;;++start){
					auto const node=queue[start];
					for(auto other: add[node]) if(result[other]!=componentId and condition(other)){
						queue.push_back(other); result[other]=componentId;
						if((int)queue.size()==size) return;
					}
				}
			};
			process(sizes[0], root, [&](int node){return dsu.root(node)==root;});
			process(sizes[1], centroid, [&](int node){return dsu.root(node)!=root;});
			return result;
		};

		for(int node=0; node<n; ++node)
			for(auto other: add[node]) if(node!=centroid and other!=centroid)
				dsu.join(node, other);

		for(int root=0; root<n; ++root)
			if(dsu.data[root]<0 and -dsu.data[root]>=sizes[0].first)
				return process(root);

		for(int index=0; index<(int)p.size(); ++index){
			auto const first=p[index], sec=q[index];
			if(first!=centroid and sec!=centroid and dsu.join(first, sec)){
				auto const root=dsu.root(first);
				if(-dsu.data[root]>=sizes[0].first){
					return process(root);
				}
			}
		}

		return std::vector<int>(n, 0);
	}
	assert(false); __builtin_unreachable();
}

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