Submission #1243052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243052		rayan_bd	Split the Attractions (IOI19_split)	C++20	7 / 100	46 ms	13768 KiB

split

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

#define all(x) x.begin(), x.end()

const int mxN = 1e5 + 100;

vector<int> adj[mxN];
vector<int> curr;

bool vis[mxN];

void dfs(int u){
	vis[u] = 1;
	curr.push_back(u);
	for(auto it : adj[u]){
		if(!vis[it]) dfs(it);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	assert(p.size() == q.size());
	assert(a + b + c == n);

	int m = (int) p.size(), grps = 0;

	for(int i = 0; i < m; ++i){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	vector<int> ans(n, -1);

	vector<pair<int, int>> ord = {{a, 1}, {b, 2}, {c, 3}};

	sort(all(ord));

	for(int i = 0; i < n; ++i){
		if(!vis[i]){
			dfs(i);
		}
		while(ord.size() > 0 && curr.size() >= ord[0].first){
			vector<int> ncurr;
			for(int i = 0; i < curr.size(); ++i){
				if(i < ord[0].first){
					ans[curr[i]] = ord[0].second;
				}else{
					ncurr.push_back(curr[i]);
				}
			}
			ord.erase(ord.begin());
			curr = ncurr;
		}
		curr.clear();
	}

	for(int i = 0; i < n; ++i){
		if(ans[i] == -1){
			for(int j = 0; j < n; ++j){
				ans[j] = 0;
			}
			return ans;
		}
	}
	return ans;
}	


/*int main(){
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);



	return 0;
}*/

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