Submission #156704

#	Time	Username	Problem	Language	Result	Execution time	Memory
156704		guangxuan	Split the Attractions (IOI19_split)	C++14	100 / 100	194 ms	31116 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define SZ(X) (int)X.size()
#define PB push_back
#define ALL(X) X.begin(),X.end()
#define RI(X) scanf("%d",&X)
#define RII(X,Y) scanf("%d%d",&X,&Y)
#define RIII(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define DRI(X) int X;scanf("%d",&X)
#define DRII(X,Y) int X,Y;scanf("%d%d",&X,&Y)
#define DRIII(X,Y,Z) int X,Y,Z;scanf("%d%d%d",&X,&Y,&Z)
#define MS0(X) memset(X,0,sizeof(X));
#define MS1(X) memset(X,-1,sizeof(X));
#define REP(I,N) for(int I=0;I<N;++I)
#define REPP(I,A,B) for(int I=A;I<B;++I)

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef pair<LL,LL> PLL;

vector<int> adj[200009],adj2[200009];
bool isap[200009];
int num[200009],low[200009],p[200009],ss[200009];
int curt=0;
int N,E;
int piva,pivb;//piva is the AP, pivb is the place to find a subtree?
vector<PII> cci;
bool possible = 1;
vector<int> ans;
int nodesleft;

void dfs(int x,int par=-1){
	num[x]=low[x]=curt++;
	ss[x]=1;
	p[x]=par;
	int children=0;
	for(int i:adj[x]){
		if(i==par)continue;
		if(num[i]==-1){
			children++;
			dfs(i,x);
			ss[x]+=ss[i];
			low[x]=min(low[x],low[i]);
			if((par!=-1&&low[i]>=num[x])||(par==-1&&children>1)){
				isap[x]=1;
			}
			adj2[x].PB(i);
		}
		else{
			low[x]=min(low[x],num[i]);
		}
	}
}

void dfstree(int x,int v){
	if(nodesleft==0)return;
	if(ans[x]!=cci[2].S)return;
	ans[x]=v;
	nodesleft --;
	for(int i:adj2[x])dfstree(i,v);
}

void dfsfree(int x,int v){
	if(nodesleft==0)return;
	if(ans[x]!=cci[2].S)return;
	ans[x]=v;
	nodesleft --;
	for(int i:adj[x])dfsfree(i,v);
}

void solve(int x){
	while(1){
		bool bigchild=0;
		for(auto i:adj2[x]){
			if(ss[i]>=cci[0].F){
				bigchild=1;
				x = i;
				break;
			}
		}
		if(!bigchild)break;
	}
	//cout << "PIVOT" << x <<endl;
	if(isap[x]){
		if(p[x]!=-1){
			if(N-ss[x]>=cci[1].F){//big parent
				nodesleft = cci[0].F;
				dfstree(x,cci[0].S);
				nodesleft = cci[1].F;
				dfsfree(p[x],cci[1].S);
			}
			else{ //b is bottom.
				ans[x] = cci[1].S;
				nodesleft = cci[1].F-1;
				for(int i:adj2[x]){
					if(low[i]<num[x])continue;
					dfstree(i,cci[1].S);//down the tree only
					if(nodesleft==0)break;
				}
				for(int i:adj2[x]){
					if(low[i]>=num[x])continue;
					dfstree(i,cci[1].S);//down the tree only
					if(nodesleft==0)break;
				}
				nodesleft = cci[0].F;
				dfsfree(p[x],cci[0].S);
				if(nodesleft)possible = 0;
			}
		}
		else{
			possible = 0;//all children <a
		}
	}
	else{ //pick till enough~!
		ans[x]=cci[0].S;
		nodesleft = cci[0].F-1;
		for(int i:adj2[x]){
			dfstree(i,cci[0].S);//down the tree only
			if(nodesleft==0)break;
		}
		nodesleft = cci[1].F;//fill the rest!
		dfsfree(p[x],cci[1].S);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n,E=SZ(p);
	cci.PB(MP(a,1));cci.PB(MP(b,2));cci.PB(MP(c,3));
	sort(ALL(cci));
	for(int i=0;i<E;i++) {
		adj[p[i]].PB(q[i]);
		adj[q[i]].PB(p[i]);
	}
	MS1(num);
	dfs(0,-1);
	for(int i=0;i<N;i++){
		ans.PB(cci[2].S);
	}
	solve(0);
	if(!possible){
		fill(ALL(ans),0);
	}
	return ans;
}

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