제출 #836075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836075		penguinman	Split the Attractions (IOI19_split)	C++17	0 / 100	28 ms	4660 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;
		}
	}

	vector<bool> used(N);
	vii v;
	rep(i,0,N){
		if(used[i]) 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(i);
		v.pb(c);
	}
	rep(i,0,v.size()){
		rep(j,0,v.size()){
			if(i == j) continue;
			if(data[0].first > v[i].size()) continue;
			if(data[1].first > v[j].size()) continue;
			for(auto el: v[i]) ans[el] = data[0].second;
			for(auto el: v[j]) ans[el] = 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) {
	if(n <= 2500) return subtask_4(n,a,b,c,p,q);
	vector<int> ans(n);
	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;
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
split.cpp:138:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |    if(data[0].first > v[i].size()) continue;
split.cpp:139:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |    if(data[1].first > v[j].size()) continue;

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