Submission #306356

#	Time	Username	Problem	Language	Result	Execution time	Memory
306356		AngelKnows	Split the Attractions (IOI19_split)	C++14	29 / 100	2068 ms	11380 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const int M=200000+10; 
const double eps=1e-5;
const int mo=1e9+7;

int n,m,A,B,C,a,b,c;
int head[N];
int nxt[2*M];
int to[2*M];
int cnt;
int dfn[N],nn;
int f[N];
int num[N];
int sz[N];
bool colored[N];
bool found=0;
bool vis[N];
int remain;
int colors[4];
int ans[N];
bool taken[N];
void color(int x,int fa) {
	colored[x]=1;
	int y;
	for (int i=head[x];i;i=nxt[i]) {
		y=to[i];
		if (y!=fa&&dfn[y]>dfn[x]) {
			color(y,x);
		}
	}
}
void add(int x,int y) {
	nxt[++cnt]=head[x];
	to[cnt]=y;
	head[x]=cnt;
	nxt[++cnt]=head[y];
	to[cnt]=x;
	head[y]=cnt;
}
void dfs(int x,int fa) {
	int y;
	sz[x]=1;
	dfn[x]=++nn;
	f[x]=nn;
	for (int i=head[x];i;i=nxt[i]) {
		y=to[i];
		if (y!=fa) {
			if (!dfn[y]) {
				dfs(y,x);
				sz[x]+=sz[y];
				num[x]++;
				f[x]=min(f[x],f[y]);
			} else f[x]=min(f[x],dfn[y]);
		}
	}
}
void solve(int x,int fa) {
	int y;
	int p=0,cntb=0,sum=0;
	for (int i=head[x];i;i=nxt[i]) {
		y=to[i];
		if (y!=fa&&dfn[y]>dfn[x]) {
			if (sz[y]>=b) {
				p=y;
				cntb++;
			}
		}
	}
	if (cntb>=2) {
		color(p,x);
		found=1;
		return;
	} else if  (cntb==1) {
		if (n-sz[p]>=c) {
			color(p,x);
			found=1;
			return;
		} else {
			solve(p,x);
		}
	} else {
		sum=n-sz[x];
		for (int i=head[x];i;i=nxt[i]) {
			y=to[i];
			if (y!=fa&&dfn[y]>dfn[x]) {
				if (f[y]<dfn[x]) {
					// 有前向边连接上树
					sum+=sz[y];
					taken[y]=1;
					if (sum>=c) {
						// find
						// 注意find处理完后要退出循环 
						for (int j=head[x];j;j=nxt[j]) {
							y=to[j];
							if (y!=fa&&dfn[y]>dfn[x]) {
								if (!taken[y]) {
									color(y,x);
								}
							}
						}
						colored[x]=1;
						found=1;
						return;
					}
				}
			}
		}
		for (int i=head[x];i;i=nxt[i]) {
			y=to[i];
			if (y!=fa&&dfn[y]>dfn[x]) {
				if (f[y]>=dfn[x]&&sz[y]>=c) {
					// find
					color(y,x);
					found=1;
					return;
				}
			}
		}
		for (int i=head[x];i;i=nxt[i]) {
			y=to[i];
			if (y!=fa&&dfn[y]>dfn[x]) {
				if (f[y]<dfn[x]&&sz[y]>=c) {
					// find
					color(y,x);
					found=1;
					return;
				}
			}
		}
		// 无解 
	}
}
void grow(int x) {
	if (remain==0) {
		return;
	}
	vis[x]=1;
	remain--;
	if (remain==0) {
		return;
	}
	int y;
	for (int i=head[x];i;i=nxt[i]) {
		y=to[i];
		if (!vis[y]&&colored[y]==colored[x]) {
			grow(y);
		}
	}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
	n=N,m=int(P.size()),a=A,b=B,c=C;
	REP(i,0,2) colors[i]=i+1;
    a=A,b=B,c=C;
    vector<int> res;
    if (c>a) {
    	swap(c,a);
    	swap(colors[2],colors[0]);
	}
    if (c>b){
		swap(c,b);
		swap(colors[2],colors[1]);
	}
    if (b>a) {
    	swap(a,b);
    	swap(colors[0],colors[1]);
	}
	for (int i=0;i<m;i++) add(P[i]+1,Q[i]+1);
	if (c>a) {
    	swap(c,a);
    	swap(colors[2],colors[0]);
	}
    if (c>b){
		swap(c,b);
		swap(colors[2],colors[1]);
	}
    if (b>a) {
    	swap(a,b);
    	swap(colors[0],colors[1]);
	}

	int maxsz=0,p=0,root=1;
	dfs(root,0);
	int y; 
	for (int i=head[root];i;i=nxt[i]) {
		y=to[i];
		//if (y!=fa) {
		// 树根没有fa 
			if (maxsz<sz[y]) {
				maxsz=sz[y];
				p=y;
			}
		//}
	}
	if (c<=maxsz&&maxsz<=a) {
		color(p,root);
		found=1;
	} else if (maxsz<c) {
		// 无解 
	} else if (maxsz>a) {
		if (n-maxsz>=c) {
			color(p,root);
			found=1;
		} else if (n-maxsz<c) {
			solve(p,root);
		}
	}
	if (found) {
		int s=0;
		FOR(i,n) if (colored[i]) s++;
		if (n-s>=s) {
			FOR(i,n) if (colored[i]) {
				remain=c;
				grow(i);
				FOR(j,n) if (vis[j]) ans[j]=colors[2];
				break;
			}
			FOR(i,n) if (!colored[i]) {
				remain=b;
				grow(i);
				FOR(j,n) {
					if (vis[j]&&!ans[j]) {
						ans[j]=colors[1];
					} else if (!vis[j]) {
						ans[j]=colors[0];
					}
				}
				break;
			}
		} else {
			FOR(i,n) if (colored[i]) {
				remain=b;
				grow(i);
				FOR(j,n) if (vis[j]) ans[j]=colors[1];
				break;
			}
			FOR(i,n) if (!colored[i]) {
				remain=c;
				grow(i);
				FOR(j,n) {
					if (vis[j]&&!ans[j]) {
						ans[j]=colors[2];
					} else if (!vis[j]) {
						ans[j]=colors[0];
					}
				}
				break;
			}
		}
		//FOR(i,n) cout<<ans[i]<<" ";
		FOR(i,n) res.pb(ans[i]); 
	} else {
		FOR(i,n) res.pb(0);
	}
	return res;
}
/*
int main() {
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}*/

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