oj.uz

Submission #287818

# Submission time Handle Problem Language Result Execution time Memory
287818 2020-09-01T03:11:06 Z user202729 Split the Attractions (IOI19_split) C++17
22 / 100
 139 ms 12540 KB 
// 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;
				assert(result[startNode]!=componentId); result[startNode]=componentId;
				if(size==1) return;
				queue.push_back(startNode);
				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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB invalid split: #1=0, #2=1, #3=2
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Incorrect 1 ms 384 KB invalid split: #1=0, #2=1, #3=2
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 127 ms 9772 KB ok, correct split
3 Correct 39 ms 3960 KB ok, correct split
4 Correct 1 ms 256 KB ok, correct split
5 Correct 131 ms 11728 KB ok, correct split
6 Correct 131 ms 11516 KB ok, correct split
7 Correct 124 ms 11388 KB ok, correct split
8 Correct 139 ms 12540 KB ok, correct split
9 Correct 138 ms 11260 KB ok, correct split
10 Correct 28 ms 3328 KB ok, no valid answer
11 Correct 44 ms 4864 KB ok, no valid answer
12 Correct 80 ms 9716 KB ok, no valid answer
13 Correct 106 ms 9592 KB ok, no valid answer
14 Correct 67 ms 9712 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 1 ms 384 KB ok, no valid answer
3 Incorrect 1 ms 384 KB invalid split: #1=0, #2=1, #3=2
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB invalid split: #1=0, #2=1, #3=2
2 Halted 0 ms 0 KB -