Submission #767696

#	Time	Username	Problem	Language	Result	Execution time	Memory
767696		ono_de206	Split the Attractions (IOI19_split)	C++14	0 / 100	0 ms	212 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);
	// 	auto dfs = [&](auto &self, int to, int fr) -> void {
	// 		P[to] = fr;
	// 		for(int x : g[to]) {
	// 			if(x ==fr) continue;
	// 			self(self, x, to);
	// 			S[to] += S[x];
	// 		}
	// 	};
	// 	dfs(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[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;
	// 			for(int j = 0; j < 3; j++) {
	// 				ans.insert(ans.end(), all(ret[i]));
	// 			}
	// 			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;
	for(int i = 0; i < 3; i++) {
		ans.insert(ans.end(), all(ret[i]));
	}
	return ans;
}

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