Submission #1105548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105548		alexander707070	Split the Attractions (IOI19_split)	C++14	40 / 100	82 ms	33608 KiB

split

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

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

int sol[MAXN],dep[MAXN],low[MAXN];
bool vis[MAXN],used[MAXN];

bool check(int x,int y){
	return x>=s[0].first and y>=s[1].first;
}

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

	used[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;

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

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

bool dfs(int x,int p){

	dep[x]=dep[p]+1; low[x]=dep[x];
	vis[x]=true; sz[x]=1;

	for(int i=0;i<v[x].size();i++){
		if(!vis[v[x][i]]){

			if(dfs(v[x][i],x))return true;

			tree[x].push_back(v[x][i]);
			sz[x]+=sz[v[x][i]];

			low[x]=min(low[x],low[v[x][i]]);
		}else if(v[x][i]!=p){
			low[x]=min(low[x],dep[v[x][i]]);
		}
	}

	vector< pair<int,int> > conn,cut;
	int sumconn=0,sumcut=0;

	for(int i:tree[x]){
		if(low[i]<=dep[x]){
			conn.push_back({sz[i],i});
			sumconn+=sz[i];
		}else{
			cut.push_back({sz[i],i});
			sumcut+=sz[i];
		}
	}

	sort(cut.begin(),cut.end());
	sort(conn.begin(),conn.end());

	/// one vertex ///

	for(int i:tree[x]){
		if(check(sz[i],n-sz[i])){
			subtree(i,0); mark(x,1);
			return true;
		}

		if(check(n-sz[i],sz[i])){
			subtree(i,1); mark(x,0);
			return true;
		}
	}

	/// a set of cut vertices ///
	int pt=0,sum=1;
	for(int i=0;i<cut.size();i++){
		while(pt<cut.size() and sum<s[0].first){
			sum+=cut[pt].first; pt++;
		}

		if(check(sum,n-sz[x]+sumconn)){

			sol[x]=s[0].second; s[0].first--; used[x]=true;
			for(int e=i;e<pt;e++)subtree(cut[e].second,0);

			mark(p,1);

			return true;
		}
		if(check(n-sz[x]+sumconn,sum)){

			sol[x]=s[1].second; s[1].first--; used[x]=true;
			for(int s=i;s<pt;s++)subtree(cut[s].second,1);
			mark(p,0);

			return true;
		}

		sum-=cut[i].first;
	}

	/// all cut vertices + a set of connected vertices ///

	sum=sumcut+1; pt=0;
	for(int i=0;i<conn.size();i++){
		while((pt<conn.size() and sum<s[0].first) or pt==i){
			sum+=conn[pt].first; pt++;
		}

		if(check(sum,n-sum)){

			sol[x]=s[0].second; s[0].first--; used[x]=true;
			for(int s=0;s<cut.size();s++)subtree(cut[s].second,0);
			for(int s=i;s<pt;s++)subtree(conn[s].second,0);
			mark(p,1);

			return true;
		}

		if(check(n-sum,sum)){

			sol[x]=s[1].second; s[1].first--; used[x]=true;
			for(int s=0;s<cut.size();s++)subtree(cut[s].second,1);
			for(int s=i;s<pt;s++)subtree(conn[s].second,1);

			mark(p,0);

			return true;
		}

		sum-=conn[i].first;
	}

	/// hopefully all cases	

	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);
	if(!dfs(1,0))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:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
split.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0;i<cut.size();i++){
      |              ~^~~~~~~~~~~
split.cpp:91:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   while(pt<cut.size() and sum<s[0].first){
      |         ~~^~~~~~~~~~~
split.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i=0;i<conn.size();i++){
      |              ~^~~~~~~~~~~~
split.cpp:120:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   while((pt<conn.size() and sum<s[0].first) or pt==i){
      |          ~~^~~~~~~~~~~~
split.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    for(int s=0;s<cut.size();s++)subtree(cut[s].second,0);
      |                ~^~~~~~~~~~~
split.cpp:137:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    for(int s=0;s<cut.size();s++)subtree(cut[s].second,1);
      |                ~^~~~~~~~~~~

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