Submission #737199

#	Time	Username	Problem	Language	Result	Execution time	Memory
737199		NeroZein	Split the Attractions (IOI19_split)	C++17	18 / 100	72 ms	11468 KiB

split

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

vector<int> find_split(int n, int a_, int b_, int c_, vector<int> pp, vector<int> q) {
	vector<int> res(n);
	vector<pair<int,int>> pts = {{a_, 1}, {b_, 2}, {c_, 3}};
	sort(pts.begin(), pts.end()); 
	int m = (int) pp.size();
	vector<vector<int>> g(n); 
	for (int i = 0; i < m; ++i) {
		g[pp[i]].push_back(q[i]);
		g[q[i]].push_back(pp[i]);
	}
	auto [s, c] = pts[0];
	vector<bool> vis(n); 
	function<void(int)> Dfs = [&](int v) {
		--s;
		res[v] = c; 
		vis[v] = true; 
		for (int u : g[v]) {
			if (!s) return; 
			if (!vis[u]) Dfs(u); 
		}
	};
	int start = 0; 
	for (int i = 1; i < n; ++i) {
		if (g[i].size() == 1) {
			start = i; 
			break; 
		}
	}
	Dfs(start); 
	s = pts[1].first;
	c = pts[1].second; 
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			Dfs(i);
			break; 
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!res[i]) {
			res[i] = pts[2].second;
		}
	}
	return res;
}

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