Submission #209942

#	Time	Username	Problem	Language	Result	Execution time	Memory
209942		Segtree	Split the Attractions (IOI19_split)	C++14	0 / 100	2100 ms	13672 KiB

split

#include"split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
ll N,A,B,C;
vector<ll> g[100010];
ll col[100010];
ll paint(ll x,ll from,ll rem,ll c){
	if(~col[x])return rem;
	if(rem<=0)return 0;
	col[x]=c;
	rem--;
	for(auto y:g[x])if(y!=from){
		rem=paint(y,x,rem,c);
	}
	return rem;
}
ll siz[100010],par[100010];
ll dfs(ll x,ll from){//部分木のサイズと親を求める
	siz[x]=1;
	par[x]=from;
	for(auto y:g[x])if(y!=from){
		siz[x]+=dfs(y,x);
	}
	return siz[x];
}
int finalcol[3];
vector<int> judge(ll root){//頂点rootを根としたdfs木で解く
	dfs(root,-1);
	rep(i,N)col[i]=-1;
	bool done=0;
	rep(i,N){
		ll x=siz[i],y=N-siz[i];
		if(A<=x&&B<=y){
			paint(i,par[i],A,0);
			paint(par[i],i,B,1);
			done=1;
			break;
		}
		if(A<=y&&B<=x){
			paint(i,par[i],B,1);
			paint(par[i],i,A,0);
			done=1;
			break;
		}
	}
	if(done==0){//
		vector<int> fans;
		rep(i,N)fans.push_back(0);
		return fans;
	}
	rep(i,N)if(col[i]==-1)col[i]=2;
	rep(i,N){
		col[i]=finalcol[col[i]];
	}
	vector<int> fans;
	rep(i,N)fans.push_back(col[i]);
	return fans;
}

vector<ll> f[3010];
bool vis[3010];
void make_dfstree(ll x,ll from){
	if(vis[x])return;
	vis[x]=1;
	if(from!=-1){
		g[x].push_back(from);
		g[from].push_back(x);
	}
	for(auto y:f[x]){
		make_dfstree(y,x);
	}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> U,vector<int> V){
	N=n,A=a,B=b,C=c;
	int M=U.size();
	rep(i,M){
		f[U[i]].push_back(V[i]);
		f[V[i]].push_back(U[i]);
	}
	{//A<=B<=Cにする
		vector<P> v;
		v.push_back(make_pair(A,1));
		v.push_back(make_pair(B,2));
		v.push_back(make_pair(C,3));
		sort(all(v));
		rep(i,3)finalcol[i]=v[i].second;
		A=v[0].first;
		B=v[1].first;
		C=v[2].first;
	}
	vector<int> res;
	rep(i,N){
		rep(j,N){
			vis[j]=0;
			g[j].clear();
		}
		make_dfstree(i,-1);
		rep(j,N)random_shuffle(all(g[j]));
		res=judge(i);
		if(res[0]!=0)return res;
	}
	return res;
}/*
int main(){
	int n,m,a,b,c;
	cin>>n>>m>>a>>b>>c;
	vector<int> U,V;
	rep(i,m){
		ll u,v;
		cin>>u>>v;
		U.push_back(u);
		V.push_back(v);
	}
	vector<int> fans=find_split(n,a,b,c,U,V);
	for(auto t:fans)cout<<t;
	cout<<endl;
}*/

Compilation message (stderr)

split.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
split.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
split.cpp:20:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")

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