Submission #719032

#	Time	Username	Problem	Language	Result	Execution time	Memory
719032		mseebacher	Split the Attractions (IOI19_split)	C++17	7 / 100	59 ms	12364 KiB

split

#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
 
#define MAX_N (int) 1e5+5
vector<int> ad[MAX_N];
vector<int> res;
vector<bool> vis(MAX_N,0);
vector<pair<int,int>> cnt;

int tiefe = 0;

void dfs(int x,int e){
	if(vis[x]) return; 
	vis[x] = 1;
	if(tiefe < cnt[0].first)
		res[x] = cnt[0].second;
	else if(tiefe >= cnt[0].first && tiefe < cnt[0].first+cnt[1].first)
		res[x] = cnt[1].second;
	else return;
	++tiefe;
	for(auto s: ad[x]){
		if(vis[s]) continue;
		dfs(s,x);
	}
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for(int i = 0;i<(int)p.size();i++){
		ad[p[i]].push_back(q[i]);
		ad[q[i]].push_back(p[i]);
	}
	res.assign(n,0);
	if(a >= n-1 || b >= n-1 || c>=n-1 || (int)p.size() < n - 1) return res;
	cnt.push_back({a,1});
	cnt.push_back({b,2});
	cnt.push_back({c,3});
	sort(cnt.begin(),cnt.end());
	for(int i = 0;i<n;i++){
		tiefe = 0;
		res.assign(n,cnt[2].second);
		dfs(i,-1);
		vis.clear();
		if(cnt[0].first+cnt[1].first == tiefe) return res;
	}
	return res;
}

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