oj.uz

Submission #284884

# Submission time Handle Problem Language Result Execution time Memory
284884 2020-08-28T07:40:38 Z Nodir_Bobiev Split the Attractions (IOI19_split) C++17
18 / 100
 130 ms 12588 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;
	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 ){
		if( sz[v] <= n - sz[v] ){
			fil(v, f, 0);
			fil(f, v, 1);
		}else{
			fil(f,v,0);
			fil(v,f,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 3 ms 2688 KB ok, correct split
3 Correct 3 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2816 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 92 ms 8952 KB ok, correct split
8 Correct 91 ms 8952 KB ok, correct split
9 Correct 105 ms 9080 KB ok, correct split
10 Correct 88 ms 8952 KB ok, correct split
11 Correct 84 ms 8956 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2720 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 95 ms 10616 KB ok, correct split
5 Correct 77 ms 9080 KB ok, correct split
6 Correct 89 ms 8952 KB ok, correct split
7 Correct 87 ms 8952 KB ok, correct split
8 Correct 127 ms 12408 KB ok, correct split
9 Correct 81 ms 8864 KB ok, correct split
10 Correct 57 ms 9120 KB ok, correct split
11 Correct 61 ms 9072 KB ok, correct split
12 Correct 60 ms 9460 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 Correct 88 ms 9832 KB ok, correct split
3 Correct 31 ms 5504 KB ok, correct split
4 Correct 3 ms 2688 KB ok, correct split
5 Correct 114 ms 11884 KB ok, correct split
6 Correct 107 ms 11512 KB ok, correct split
7 Correct 105 ms 11512 KB ok, correct split
8 Correct 130 ms 12588 KB ok, correct split
9 Correct 115 ms 11512 KB ok, correct split
10 Incorrect 25 ms 4992 KB invalid split: #1=29, #2=11111, #3=22193
11 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 3 ms 2688 KB ok, correct split
3 Correct 3 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2816 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 92 ms 8952 KB ok, correct split
8 Correct 91 ms 8952 KB ok, correct split
9 Correct 105 ms 9080 KB ok, correct split
10 Correct 88 ms 8952 KB ok, correct split
11 Correct 84 ms 8956 KB ok, correct split
12 Correct 2 ms 2720 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 95 ms 10616 KB ok, correct split
16 Correct 77 ms 9080 KB ok, correct split
17 Correct 89 ms 8952 KB ok, correct split
18 Correct 87 ms 8952 KB ok, correct split
19 Correct 127 ms 12408 KB ok, correct split
20 Correct 81 ms 8864 KB ok, correct split
21 Correct 57 ms 9120 KB ok, correct split
22 Correct 61 ms 9072 KB ok, correct split
23 Correct 60 ms 9460 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Correct 88 ms 9832 KB ok, correct split
26 Correct 31 ms 5504 KB ok, correct split
27 Correct 3 ms 2688 KB ok, correct split
28 Correct 114 ms 11884 KB ok, correct split
29 Correct 107 ms 11512 KB ok, correct split
30 Correct 105 ms 11512 KB ok, correct split
31 Correct 130 ms 12588 KB ok, correct split
32 Correct 115 ms 11512 KB ok, correct split
33 Incorrect 25 ms 4992 KB invalid split: #1=29, #2=11111, #3=22193
34 Halted 0 ms 0 KB -