oj.uz

답안 #284244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284244 2020-08-27T04:53:03 Z Nodir_Bobiev Split the Attractions (IOI19_split) C++17
18 / 100
 132 ms 12408 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 ){
	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(){
	throw;
	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

# 결과 실행 시간 메모리 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 3 ms 2944 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 99 ms 8952 KB ok, correct split
8 Correct 95 ms 8952 KB ok, correct split
9 Correct 98 ms 8952 KB ok, correct split
10 Correct 119 ms 8952 KB ok, correct split
11 Correct 85 ms 8952 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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 101 ms 10616 KB ok, correct split
5 Correct 78 ms 9080 KB ok, correct split
6 Correct 92 ms 8952 KB ok, correct split
7 Correct 90 ms 8952 KB ok, correct split
8 Correct 132 ms 12408 KB ok, correct split
9 Correct 83 ms 8952 KB ok, correct split
10 Correct 59 ms 9072 KB ok, correct split
11 Correct 61 ms 9072 KB ok, correct split
12 Correct 63 ms 9456 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2688 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 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 3 ms 2944 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 99 ms 8952 KB ok, correct split
8 Correct 95 ms 8952 KB ok, correct split
9 Correct 98 ms 8952 KB ok, correct split
10 Correct 119 ms 8952 KB ok, correct split
11 Correct 85 ms 8952 KB ok, correct split
12 Correct 2 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 101 ms 10616 KB ok, correct split
16 Correct 78 ms 9080 KB ok, correct split
17 Correct 92 ms 8952 KB ok, correct split
18 Correct 90 ms 8952 KB ok, correct split
19 Correct 132 ms 12408 KB ok, correct split
20 Correct 83 ms 8952 KB ok, correct split
21 Correct 59 ms 9072 KB ok, correct split
22 Correct 61 ms 9072 KB ok, correct split
23 Correct 63 ms 9456 KB ok, correct split
24 Runtime error 6 ms 5248 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -