oj.uz

Submission #284841

# Submission time Handle Problem Language Result Execution time Memory
284841 2020-08-28T06:43:59 Z Nodir_Bobiev Split the Attractions (IOI19_split) C++17
18 / 100
 124 ms 11260 KB 
#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 ){
	//cout <<v << ' '<< f << endl;
	vector < pair < int, int > >children;
	bool t = false;
	for( auto to: gr[v] ){
		if( to != f && sz[to] >= cl[0].first ){
			t = true;
		}
	}
	if( sz[v] < cl[0].first ) t = true;
	if( !t ){
		fil(v, f, 0);
		fil(f, v, 1);
		return true;
	}
	for( auto to: gr[v] ){
		if( to != f ){
			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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 3 ms 2688 KB ok, correct split
7 Correct 120 ms 8952 KB ok, correct split
8 Correct 100 ms 8956 KB ok, correct split
9 Correct 88 ms 8824 KB ok, correct split
10 Correct 95 ms 8824 KB ok, correct split
11 Correct 88 ms 8824 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2816 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 96 ms 9976 KB ok, correct split
5 Correct 81 ms 9080 KB ok, correct split
6 Correct 90 ms 8952 KB ok, correct split
7 Correct 96 ms 8908 KB ok, correct split
8 Correct 124 ms 11260 KB ok, correct split
9 Correct 98 ms 8824 KB ok, correct split
10 Correct 58 ms 9200 KB ok, correct split
11 Correct 58 ms 9076 KB ok, correct split
12 Correct 60 ms 9592 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Incorrect 104 ms 9788 KB invalid split: #1=20000, #2=21840, #3=58160
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 3 ms 2688 KB ok, correct split
7 Correct 120 ms 8952 KB ok, correct split
8 Correct 100 ms 8956 KB ok, correct split
9 Correct 88 ms 8824 KB ok, correct split
10 Correct 95 ms 8824 KB ok, correct split
11 Correct 88 ms 8824 KB ok, correct split
12 Correct 2 ms 2688 KB ok, correct split
13 Correct 2 ms 2816 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 96 ms 9976 KB ok, correct split
16 Correct 81 ms 9080 KB ok, correct split
17 Correct 90 ms 8952 KB ok, correct split
18 Correct 96 ms 8908 KB ok, correct split
19 Correct 124 ms 11260 KB ok, correct split
20 Correct 98 ms 8824 KB ok, correct split
21 Correct 58 ms 9200 KB ok, correct split
22 Correct 58 ms 9076 KB ok, correct split
23 Correct 60 ms 9592 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Incorrect 104 ms 9788 KB invalid split: #1=20000, #2=21840, #3=58160
26 Halted 0 ms 0 KB -