Submission #1042365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042365		HD1	Split the Attractions (IOI19_split)	C++14	0 / 100	3 ms	6748 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) ll(s.size())
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
const ll MAX=1e5+5;
using namespace std;
vector<ll> gfo[MAX];
ll q[MAX];
bool vst[MAX];
ll cont=0;
ll marc;
ll a, b, c, n;
void dfs_b(int u){
	if(cont==b)return;
	cont++;
	q[u]=marc;
	vst[u]=true;
	if(cont==b)return;
	for(auto v: gfo[u]){
		if(!vst[v]){
			dfs_b(v);
		}
	}
	return;
}
void dfs_a(int u){
	if(cont==a)return;
	cont++;
	q[u]=marc;
	vst[u]=true;
	if(cont==a)return;
	for(auto v: gfo[u]){
		if(!vst[v]){
			dfs_a(v);
		}
	}
	return;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> u, vector<int> v) {
	a=A;
	b=B;
	c=C;
	n=N;
	vector<int> res;
	for(int i=0; i<n; i++){
		gfo[u[i]].pb(v[i]);
		gfo[v[i]].pb(u[i]);
	}
	if(a==1){
		marc=2;
		dfs_b(0);
		marc=1;
		for(int i=0; i<n; i++){
			if(q[i]==0){
				q[i]=marc;
				break;
			}
		}
		marc=3;
		for(int i=0; i<n; i++){
			if(q[i]==0){
				q[i]=marc;
			}
			res.pb(q[i]);
		}
		return res;
	}
	//////////////////
	ll aux=0;
	for(int i=0; i<n; i++){
		if(sz(gfo[i])==1){
			aux=i;
			break;
		}
	}
	marc=2;
	dfs_b(aux);
	for(int i=0; i<n; i++){
		if(sz(gfo[i])==1 && !vst[i]){
			aux=i;
			break;
		}
		if(!vst[i])aux=i;
	}
	marc=1;
	cont=0;
	dfs_a(aux);
	marc=3;
	for(int i=0; i<n; i++){
		if(!vst[i]){
			q[i]=marc;
		}
	}
	for(int i=0; i<n; i++){
		res.pb(q[i]);
	}
	return res;
}
/*
8 8
2 3 3
0 1
1 6
6 7
7 5
5 4
4 3
3 2
0 2

8 7
2 3 3
0 1
1 2
1 7
1 3
3 4
4 5
4 6

*/

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