Submission #1243114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243114		rayan_bd	Split the Attractions (IOI19_split)	C++20	11 / 100	51 ms	12996 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);
	assert(a == 1);

	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 = {{b, 2}, {c, 3}};

	sort(all(ord));
	bool ok = 0;

	for(int i = 0; i < n; ++i){
		if(!vis[i]){
			dfs(i);
		}
		if(curr.size() >= ord[0].first){
			for(int i = 0; i < ord[0].first; ++i){
				ans[curr[i]] = ord[0].second;
			}
			ord.erase(ord.begin());
			ok = 1;
			break;
		}
		curr.clear();
	}

	if(!ok){
		for(auto &it : ans) it = 0;
		return ans;
	}

	for(int i = 0; i < n; ++i){
		if(ans[i] == -1 && a == 1) ans[i] = 1, --a;
		else if(ans[i] == -1) ans[i] = ord[0].second;
	}

	return ans;
}	


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



	return 0;
}*/

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