Submission #1042363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042363		byakko	Split the Attractions (IOI19_split)	C++17	11 / 100	41 ms	12884 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 100;

vector<int> adj[N];
int deg[N];
bool vis[N];

void dfs(int r, int cnt, int l, vector<int>& ans) {
	queue<int> q;
	vis[r] = true;
	q.push(r);
	while(!q.empty() && cnt) {
		int v = q.front();
		q.pop();
		cnt--;
		ans[v] = l;
		for(auto u: adj[v]) if(!vis[u]) {
			vis[u] = true;
			q.push(u);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = p.size();
	for(int i = 0; i < m; i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
		deg[p[i]]++;
		deg[q[i]]++;
	}
	vector<int> ans(n);
	if(a == 1) {
		dfs(0, b, 2, ans);
		for(int i = 0; i < n; i++) if(ans[i] == 0) {
			if(a) {
				ans[i] = 1;
				a--;
			} else ans[i] = 3;
		}
	} else {
		bool found = 0;
		for(int i = 0; i < n; i++) {
			if(deg[i] == 1) {
				if(!found) {
					dfs(i, a, 1, ans);
					found = true;
				} else
					dfs(i, b, 2, ans);
			}
		}
		if(!found) {
			dfs(0, a, 1, ans);
			for(int i = 1; i < n; i++) {
				if(!vis[i]) {
					dfs(i, b, 2, ans);
					break;
				}
			}
		}
		for(int i = 0; i < n; i++) if(ans[i] == 0) {
			ans[i] = 3;
		}
	}
	return ans;
}

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