oj.uz

Submission #283923

# Submission time Handle Problem Language Result Execution time Memory
283923 2020-08-26T09:40:48 Z Nodir_Bobiev Split the Attractions (IOI19_split) C++17
18 / 100
 121 ms 10232 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;
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

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.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 2 ms 2688 KB ok, correct split
7 Correct 89 ms 7728 KB ok, correct split
8 Correct 95 ms 7816 KB ok, correct split
9 Correct 94 ms 7748 KB ok, correct split
10 Correct 90 ms 7800 KB ok, correct split
11 Correct 92 ms 7768 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 105 ms 8952 KB ok, correct split
5 Correct 77 ms 7928 KB ok, correct split
6 Correct 101 ms 7800 KB ok, correct split
7 Correct 95 ms 7712 KB ok, correct split
8 Correct 121 ms 10232 KB ok, correct split
9 Correct 86 ms 8952 KB ok, correct split
10 Correct 75 ms 9140 KB ok, correct split
11 Correct 62 ms 9120 KB ok, correct split
12 Correct 72 ms 9456 KB ok, correct split

Subtask #3
0 / 22.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 #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 2 ms 2688 KB ok, correct split
7 Correct 89 ms 7728 KB ok, correct split
8 Correct 95 ms 7816 KB ok, correct split
9 Correct 94 ms 7748 KB ok, correct split
10 Correct 90 ms 7800 KB ok, correct split
11 Correct 92 ms 7768 KB ok, correct split
12 Correct 3 ms 2688 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 105 ms 8952 KB ok, correct split
16 Correct 77 ms 7928 KB ok, correct split
17 Correct 101 ms 7800 KB ok, correct split
18 Correct 95 ms 7712 KB ok, correct split
19 Correct 121 ms 10232 KB ok, correct split
20 Correct 86 ms 8952 KB ok, correct split
21 Correct 75 ms 9140 KB ok, correct split
22 Correct 62 ms 9120 KB ok, correct split
23 Correct 72 ms 9456 KB ok, correct split
24 Incorrect 2 ms 2688 KB WA in grader: Invalid length of the result.
25 Halted 0 ms 0 KB -