제출 #836197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836197		penguinman	Split the Attractions (IOI19_split)	C++17	40 / 100	90 ms	23384 KiB

split

#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) {
	ll N = n;
	std::random_device rnd;
	std::mt19937_64 mt(rnd());

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

	{
		vector<pii> e;
		rep(i,0,p.size()) e.pb(mp(p[i],q[i]));
		std::shuffle(all(e), mt);
		rep(i,0,p.size()) std::tie(p[i], q[i]) = e[i];
	}

	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;
	};

	vi subtree(N);

	vii d_edge(N);

	std::function<void(ll)> dfs_subtree = [&](ll now){
		subtree[now] = 1;
		for(auto next: edge[now]){
			if(subtree[next]) continue;
			d_edge[now].pb(next);
			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: d_edge[now]){
			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;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> subtask_4(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:94:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   94 |    if(v[j].size() < data[0].first) continue;
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~
split.cpp:95:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   95 |    if(sum-v[j].size() < data[1].first) continue;
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
split.cpp:106:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  106 |    if(v[j].size() < data[1].first) continue;
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~
split.cpp:107:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
  107 |    if(sum-v[j].size() < data[0].first) continue;
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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