Submission #1105518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105518		alexander707070	Split the Attractions (IOI19_split)	C++14	18 / 100	2061 ms	24648 KiB

split

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

int n,m,li[MAXN],tim,sz[MAXN];
pair<int,int> s[3];
vector<int> v[MAXN],ans,tree[MAXN];
int in[MAXN];

int sol[MAXN];
bool vis[MAXN];

void subtree(int x,int id){
	if(s[id].first==0)return;

	vis[x]=true;
	sol[x]=s[id].second;
	s[id].first--;

	for(int i:tree[x]){
		subtree(i,id);
	}
}

void mark(int x,int id){
	if(s[id].first==0)return;

	vis[x]=true;
	sol[x]=s[id].second;
	s[id].first--;

	for(int i:v[x]){
		if(vis[i])continue;
		mark(i,id);
	}
}

bool dfs(int x,int p){
	li[x]=tim; sz[x]=1; in[x]=1;

	for(int i=0;i<v[x].size();i++){
		if(li[v[x][i]]==tim)continue;

		tree[x].push_back(v[x][i]);

		if(dfs(v[x][i],x))return true;
		sz[x]+=sz[v[x][i]];
	}

	in[x]=2;

	if(sz[x]>=s[0].first and n-sz[x]>=s[1].first){
		subtree(x,0);
		mark(p,1);

		return true;
	}

	if(sz[x]>=s[1].first and n-sz[x]>=s[0].first){
		subtree(x,1);
		mark(p,0);

		return true;
	}

	return false;
}

vector<int> find_split(int N, int A, int B, int C,vector<int> p,vector<int> q){
	n=N; m=int(p.size());

	s[0]={A,1}; s[1]={B,2}; s[2]={C,3};
	sort(s,s+3);

	for(int i=1;i<=m;i++){
		v[p[i-1]+1].push_back(q[i-1]+1);
		v[q[i-1]+1].push_back(p[i-1]+1);
	}

	ans.resize(n);

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			tree[f].clear(); in[f]=0;
		}
		tim++; 
		
		if(dfs(i,0))break;
		if(i==n)return ans;
	}

	for(int i=1;i<=n;i++){
		if(sol[i]==0)sol[i]=s[2].second;
	}

	for(int i=1;i<=n;i++)ans[i-1]=sol[i];
	return ans;
}
 
/*int main(){
	
	ans=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});

	for(int i:ans){
		cout<<i<<" ";
	}
 
	return 0;
}*/

Compilation message (stderr)

split.cpp: In function 'bool dfs(int, int)':
split.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

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