Submission #1160715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160715		hyakup	Split the Attractions (IOI19_split)	C++20	29 / 100	544 ms	1114112 KiB

split

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

using namespace std;

vector<vector<int>> adj;
vector<int> resp, sub, pai;

void dfs( int cur, int ancestor ){
	pai[cur] = ancestor;
	sub[cur] = 1;
	for( int viz : adj[cur] ) if( viz != ancestor ){
		dfs( viz, cur );
		sub[cur] +=  sub[viz];
	}
}

void dfs( int cur, int last, int &resto, int flag ){
	if( resto == 0 ) return;
	resp[cur] = flag; resto--;
	for( int viz : adj[cur] ) if( viz != last ) dfs( viz, cur, 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);
	sub.resize(n);
	pai.resize(n);

	for( int i = 0; i < n - 1; 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, 0 );



	bool ok = false;
	for( int i = 1; i < n; i++ ){
		if( sub[i] >= comps[0].first && n - sub[i] >= comps[1].first ){
			dfs( i, pai[i], comps[0].first, comps[0].second );
			dfs( pai[i], i, comps[1].first, comps[1].second );
			ok = true;
			break;
		}
		else if( sub[i] >= comps[1].first && n - sub[i] >= comps[0].first ){
			dfs( pai[i], i, comps[0].first, comps[0].second );
			dfs( i, pai[i], comps[1].first, comps[1].second );
			ok = true;
			break;
		}
	}
	if( !ok ) return resp;

	for( int &x : resp ) if( x == 0 ) x = comps[2].second;

	return resp;
}

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