Submission #1160711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160711		hyakup	Split the Attractions (IOI19_split)	C++20	11 / 100	70 ms	10568 KiB

split

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

using namespace std;

vector<vector<int>> adj;
vector<int> resp;

void dfs( int cur, int& resto, int flag ){
	if( resp[cur] != 0 || resto == 0 ) return;
	resp[cur] = flag; resto--;
	for( int viz : adj[cur] ) dfs( viz, resto, flag );
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	adj.resize(n);
	resp.resize(n);

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

	vector<pair<int, int>> comps = { make_pair( a, 1 ), make_pair( b, 2 ), make_pair( c, 3 ) };
	sort( comps.begin(), comps.end() );

	dfs( 0, comps[1].first, comps[1].second );

	bool ok = false;
	for( int i = 0; i < n; i++ ) if( resp[i] == 0 ){
		if( !ok ){ resp[i] = comps[0].second; ok = true; }
		else resp[i] = comps[2].second;
	}

	return resp;
}

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