Submission #836183

#	Time	Username	Problem	Language	Result	Execution time	Memory
836183		penguinman	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KiB

rect

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

#ifndef EVAL
#include "grader.cpp"
#endif

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);

vector<int> subtask_4(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	ll N = n;

	vector<pii> data = {mp(a,1), mp(b,2), mp(c,3)};
	sort(all(data));

	vii edge(N);
	rep(i,0,p.size()){
		edge[p[i]].pb(q[i]);
		edge[q[i]].pb(p[i]);
	}

	vector<int> ans(N, data[2].second);


	auto modify_all = [&](){
		rep(i,0,2){
			rep(j,0,N){
				if(ans[j] == data[i].second){
					vector<bool> visited(N);
					ll cnt = 0;
					std::function<void(ll)> modify = [&](ll now){
						if(cnt < data[i].first){
							cnt++;
						}
						else{
							ans[now] = data[2].second;
						}
						visited[now] = true;
						for(auto next: edge[now]){
							if(visited[next]) continue;
							if(ans[next] != data[i].second) continue;
							modify(next);
						}
					};
					modify(j);
					break;
				}
			}
		}
		return;
	};

	rep(i,0,N){
		vector<bool> used(N);
		used[i] = true;
		vii v;
		for(auto next: edge[i]){
			if(used[next]) continue;
			vi c;
			std::function<void(ll)> dfs = [&](ll now){
				c.pb(now);
				used[now] = true;
				for(auto nex: edge[now]){
					if(used[nex]) continue;
					dfs(nex);
				}
			};
			dfs(next);
			v.pb(c);
		}
		ll sum = 1;
		rep(j,0,v.size()){
			sum += v[j].size();
		}
		rep(j,0,v.size()){
			if(v[j].size() < data[0].first) continue;
			if(sum-v[j].size() < data[1].first) continue;
			rep(k,0,v.size()){
				if(j == k) continue;
				for(auto el: v[k]) ans[el] = data[1].second;
			}
			ans[i] = data[1].second;
			for(auto el: v[j]) ans[el] = data[0].second;
			modify_all();
			return ans;
		}
		rep(j,0,v.size()){
			if(v[j].size() < data[1].first) continue;
			if(sum-v[j].size() < data[0].first) continue;
			rep(k,0,v.size()){
				if(j == k) continue;
				for(auto el: v[k]) ans[el] = data[0].second;
			}
			ans[i] = data[0].second;
			for(auto el: v[j]) ans[el] = data[1].second;
			modify_all();
			return ans;
		}
	}

	ans.assign(N,0);
	return ans;
}

struct union_find{
	ll N;
	vi par;
	union_find(int n): N(n){
		par.resize(N);
		rep(i,0,N) par[i] = i;
	}
	ll root(ll now){
		if(par[now] == now) return now;
		return par[now] = root(par[now]);
	}
	bool same(ll l, ll r){
		return root(l) == root(r);
	}
	void merge(ll l, ll r){
		l = root(l);
		r = root(r);
		if(l == r) return;
		par[l] = r;
	}
};


vector<int> subtask_1_2_3(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	ll N = n;

	vector<pii> data = {mp(a,1), mp(b,2), mp(c,3)};
	sort(all(data));

	vii edge(N);
	union_find tree(N);
	rep(i,0,p.size()){
		if(tree.same(p[i], q[i])) continue;
		tree.merge(p[i], q[i]);
		edge[p[i]].pb(q[i]);
		edge[q[i]].pb(p[i]);
	}

	vector<int> ans(N, data[2].second);

	auto modify_all = [&](){
		rep(i,0,2){
			rep(j,0,N){
				if(ans[j] == data[i].second){
					vector<bool> visited(N);
					ll cnt = 0;
					std::function<void(ll)> modify = [&](ll now){
						if(cnt < data[i].first){
							cnt++;
						}
						else{
							ans[now] = data[2].second;
						}
						visited[now] = true;
						for(auto next: edge[now]){
							if(visited[next]) continue;
							if(ans[next] != data[i].second) continue;
							modify(next);
						}
					};
					modify(j);
					break;
				}
			}
		}
		return;
	};

	vi subtree(N);

	std::function<void(ll)> dfs_subtree = [&](ll now){
		subtree[now] = 1;
		for(auto next: edge[now]){
			if(subtree[next]) continue;
			dfs_subtree(next);
			subtree[now] += subtree[next];
		}
	};

	dfs_subtree(0);

	std::function<void(ll, ll)> dfs_coloring = [&](ll now, ll color){
		ans[now] = color;
		for(auto next: edge[now]){
			if(subtree[next] > subtree[now]) continue;
			dfs_coloring(next, color);
		}
	};

	rep(i,1,N){
		if(subtree[i] < data[0].first) continue;
		if(N-subtree[i] < data[1].first) continue;
		ans.assign(N,data[1].second);
		dfs_coloring(i, data[0].second);
		modify_all();
		return ans;
	}

	rep(i,1,N){
		if(subtree[i] < data[1].first) continue;
		if(N-subtree[i] < data[0].first) continue;
		ans.assign(N, data[0].second);
		dfs_coloring(i, data[1].second);
		modify_all();
		return ans;
	}

	ans.assign(N,0);
	return ans;
}


std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
	return subtask_1_2_3(n,a,b,c,p,q);
}

Compilation message (stderr)

rect.cpp:1:10: fatal error: split.h: No such file or directory
    1 | #include "split.h"
      |          ^~~~~~~~~
compilation terminated.