Submission #283923

#	Time	Username	Problem	Language	Result	Execution time	Memory
283923		Nodir_Bobiev	Split the Attractions (IOI19_split)	C++17	18 / 100	121 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;
vector < int > gr[N];

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;	
}
vector < int > Subtask3(){
	return {};
}
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();
	}
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^

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