Submission #283994

#	Time	Username	Problem	Language	Result	Execution time	Memory
283994		Nodir_Bobiev	Split the Attractions (IOI19_split)	C++17	18 / 100	125 ms	10232 KiB

split

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 100;
bool sub1 = true, sub2 = true, sub3 = true, sub4 = true;
int n, m, A, B, C, sz[N];
vector < int > ans;
vector < int > gr[N];
vector < pair < int, int > >cl;

vector < int > Subtask1(){
	vector < int > ans(n,0);
	int fath = -1, start = 0;
	for( int i = 0; i < n; i ++ ){
		if( gr[i].size() == 1 )start = i;
	}
	while( A + B + C > 0 ){
		if( A > 0 ){
			ans[start] = 1;
			A--;
		}else if( B > 0 ){
			ans[start] = 2;
			B --;
		}else{
			ans[start] = 3;
			C --;
		}
		if( gr[start][0] != fath ){
			fath = start;
			start = gr[start][0];
		}else if( gr[start].size() > 1 ){
			fath = start;
			start = gr[start][1];
		}
	}return ans;
}
vector < int > Subtask2(){
	vector < int > ans(n, 3);
	queue < int > q;
	q.push(0); ans[0] = 2;B--;
	while(!q.empty() && B > 0){
		int v = q.front();q.pop();
		for( auto to: gr[v] ){
			if( B > 0 && ans[to] == 3 ){
				q.push(to); ans[to] = 2; B--;
			}
		}
	}for( int i = 0; i < n; i ++ )if( ans[i] == 3 ){ans[i]=1;break;}
	return ans;	
}
void build( int v, int f ){
	sz[v] = 1;
	for( auto to: gr[v] ){
		if( to != f ){
			build(to, v);
			sz[v] += sz[to];
		}
	}
}
void fil( int v, int f, int x ){
	if( cl[x].first == 0 ) return;
	ans[v] = cl[x].second;
	cl[x].first --;
	for( auto to: gr[v] ){
		if( to != f ) fil(to, v, x);
	}
}
bool dfs( int v, int f ){
	vector < pair < int, int > >children;
	for( auto to: gr[v] ){
		children.push_back({sz[to], to});
	}
	sort(children.begin(),children.end());
	for( size_t i = 0; i < children.size(); i ++ ){
		if( children[i].first >= cl[0].first && sz[v] - children[i].first >= cl[1].first ){
			fil(children[i].second, v, 0);
			ans[v] = cl[1].second; cl[1].first--;
			for( size_t j = 0; j < i; j ++ )fil(children[j].second, v, 1);
			for( size_t j = i+1; j < children.size(); j ++ )fil(children[j].second, v, 1);
			return true;
		}
	}
	for( auto to: gr[v] ){
		if( to != f ){
			sz[v] -= sz[to]; sz[to] += sz[v];
			if( dfs(to,v) ) return true;
		}
	}
	return false;
}
vector < int > Subtask3(){
	cl.push_back({A,1}); cl.push_back({B,2}); cl.push_back({C,3});
	sort(cl.begin(), cl.end());
	ans.resize(n); build(0, -1);
	if( dfs(0,-1) ){
		for( int i = 0; i < n; i ++ )if( !ans[i] ) ans[i] = cl[2].second;
	}return ans;
}
vector < int > Subtask4(){
	return {};
}

vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> pp, vector<int> qq) {
	n = nn; m = pp.size(); A = aa; B = bb; C = cc;
	if( m >= n )sub3 = false;
	if( n > 2500 || m > 5000 ) sub4 = false;
	if( A > 1 ) sub2 = false;

	for( int i = 0; i < m; i ++ ){
		gr[pp[i]].push_back(qq[i]);
		gr[qq[i]].push_back(pp[i]);
	}
	for( int i = 0; i < n; i ++ ){
		if( gr[i].size() > 2 )sub1 = false;
	}
	if( sub1 ){
		return Subtask1();
	}
	if( sub2 ){
		return Subtask2();
	}
	if( sub3 ){
		return Subtask3();
	}
	if( sub4 ){
		return Subtask4();
	}
	return {};
}

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