oj.uz

Submission #306371

# Submission time Handle Problem Language Result Execution time Memory
306371 2020-09-25T10:13:58 Z AngelKnows Split the Attractions (IOI19_split) C++14
29 / 100
 2000 ms 11380 KB 
#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);

	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) 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 0 ms 384 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Correct 1 ms 512 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 68 ms 11256 KB ok, correct split
8 Correct 61 ms 9720 KB ok, correct split
9 Correct 63 ms 9332 KB ok, correct split
10 Correct 64 ms 11252 KB ok, correct split
11 Correct 70 ms 11380 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 1 ms 384 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Execution timed out 2037 ms 9208 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 58 ms 6644 KB ok, correct split
3 Correct 21 ms 3072 KB ok, correct split
4 Correct 0 ms 384 KB ok, correct split
5 Correct 61 ms 8180 KB ok, correct split
6 Correct 65 ms 8180 KB ok, correct split
7 Correct 66 ms 7924 KB ok, correct split
8 Correct 64 ms 8692 KB ok, correct split
9 Correct 65 ms 7796 KB ok, correct split
10 Correct 17 ms 2432 KB ok, no valid answer
11 Correct 24 ms 3328 KB ok, no valid answer
12 Correct 47 ms 6004 KB ok, no valid answer
13 Correct 50 ms 6132 KB ok, no valid answer
14 Correct 45 ms 5620 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 1 ms 384 KB ok, no valid answer
3 Correct 1 ms 384 KB ok, correct split
4 Correct 0 ms 384 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 0 ms 384 KB ok, correct split
7 Correct 1 ms 384 KB ok, correct split
8 Incorrect 1 ms 384 KB invalid split: #1=4, #2=5, #3=7
9 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 0 ms 384 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Correct 1 ms 512 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 68 ms 11256 KB ok, correct split
8 Correct 61 ms 9720 KB ok, correct split
9 Correct 63 ms 9332 KB ok, correct split
10 Correct 64 ms 11252 KB ok, correct split
11 Correct 70 ms 11380 KB ok, correct split
12 Correct 1 ms 384 KB ok, correct split
13 Correct 1 ms 384 KB ok, correct split
14 Correct 1 ms 384 KB ok, correct split
15 Execution timed out 2037 ms 9208 KB Time limit exceeded
16 Halted 0 ms 0 KB -