제출 #767703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767703		ono_de206	Split the Attractions (IOI19_split)	C++14	40 / 100	60 ms	18356 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
	int m = q.size();
	vector<vector<int>> g(n);
	for(int i = 0; i < m; i++) {
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	vector<vector<int>> ret(3);
	vector<int> tmp, a(3), vis(n);
	tmp.pb(A); tmp.pb(B); tmp.pb(C);
	for(int i = 0; i < 3; i++) {
		a[i] = i;
	}
	sort(all(a), [&](int x, int y) {
		return tmp[x] < tmp[y];
	});

	auto bfs = [&](int st, int sz) -> vector<int> {
		queue<int> q;
		q.push(st);
		vis[st] = 1;

		vector<int> ret;
		ret.pb(st);

		while(q.size() && (int)ret.size() < sz) {
			int x = q.front(); q.pop();
			for(int y : g[x]) {
				if(vis[y] || (int)ret.size() == sz) continue;
				vis[y] = 1;
				ret.pb(y);
				q.push(y);
			}
		}
		return ret;
	};

	if(m == n - 1) {
		vector<int> S(n, 1), P(n);
		function<void(int, int)> dfs = [&](int to, int fr) -> void {
			P[to] = fr;
			for(int x : g[to]) {
				if(x ==fr) continue;
				dfs(x, to);
				S[to] += S[x];
			}
		};
		dfs(0, -1);
		for(int i = 0; i < n; i++) {
			if((S[i] >= tmp[a[0]] && n - S[i] >= tmp[a[1]]) || (S[i] >= tmp[a[1]] && n - S[i] >= tmp[a[0]])) {
				g[i].erase(find(all(g[i]), P[i]));
				g[P[i]].erase(find(all(g[P[i]]), i));
				if(S[i] >= tmp[a[0]] && n - S[i] >= tmp[a[1]]) {
					ret[a[0]] = bfs(i, tmp[a[0]]);
					ret[a[1]] = bfs(P[i], tmp[a[1]]);
				} else {
					ret[a[1]] = bfs(i, tmp[a[1]]);
					ret[a[0]] = bfs(P[i], tmp[a[0]]);
				}
				for(int j = 0; j < n; j++) {
					if(vis[j] == 0) ret[a[2]].pb(j);
				}
				vector<int> ans(n);
				for(int j = 0; j < 3; j++) {
					for(int x : ret[j]) {
						ans[x] = j + 1;
					}
				}
				return ans;
			}
		}
		return vector<int>(n, 0);
	}
	ret[a[1]] = bfs(0, tmp[a[1]]);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			ret[a[0]] = bfs(i, tmp[a[0]]);
			break;
		}
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			ret[a[2]].pb(i);
		}
	}
	vector<int> ans(n);
	for(int j = 0; j < 3; j++) {
		for(int x : ret[j]) {
			ans[x] = j + 1;
		}
	}
	return ans;
}

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