Submission #836679

#	Time	Username	Problem	Language	Result	Execution time	Memory
836679		Antekb	Split the Attractions (IOI19_split)	C++17	22 / 100	118 ms	32612 KiB

split

#include<bits/stdc++.h>
#include "split.h"
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using ll = long long;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=1e5+5;

vi E[N], E2[N], E3[N];
vi kto[N];
int pre[N], lo[N], par[N], czy_art[N], czy_root[N], bcc[N], roz[N], siz[N];
int n;
int cent;
int wsk=1;
void dfs(int v){
	lo[v]=pre[v]=wsk++;
	for(int u:E[v]){
		if(!pre[u]){
			par[u]=v;
			dfs(u);
			lo[v]=min(lo[v], lo[u]);
		}
		else if(u!=par[v]){
			lo[v]=min(lo[v], pre[u]);
		}
	}
	if(par[v]!=-1 && lo[v]>=pre[par[v]]){
		//deb(v, par[v]);
		czy_art[par[v]]=1;
	}
}
void color(int v, int c){
	if(v==c)czy_root[v]=1;
	bcc[v]=c;
	roz[c]++;
	kto[c].pb(v);
	for(int u:E[v]){
		if(v==par[u]){
			if(!czy_art[u] && !czy_art[v])color(u, c);
			else color(u, u);
		}
	}
}
void dfs_cent(int v){
	siz[v]=roz[v];
	bool czy=1;
	for(int u:E2[v]){
		if(!siz[u]){
			E3[u].pb(v);
			E3[v].pb(u);
			dfs_cent(u);
			siz[v]+=siz[u];
			if(2*siz[u]>n)czy=0;
		}
	}
	if(czy && 2*(n-siz[v])<=n){
		cent=v;
	}
}
void dfs_sz(int v){
	siz[v]=roz[v];
	for(int u:E3[v]){
		if(u!=par[v]){
			par[u]=v;
			dfs_sz(u);
			siz[v]+=siz[u];
		}
	}
}
vi find(int a, vi dozw){
	//deb(a, dozw[0], dozw[1], dozw[2]);
	vi V;
	for(int i=0; i<n; i++){
		if(dozw[i]){
			dozw[i]=0;
			V.pb(i);
			break;
		}
	}
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		//deb(v);
		for(int u:E[v]){
			if(dozw[u]){
				dozw[u]=0;
				V.pb(u);
			}
		}
	}
	for(int i=0; i<n; i++){
		if(dozw[i])assert(false);
	}
	//if(V.size()<a)return V;
	//assert(V.size()>=a);
	V.resize(a);
	return V;
}
vi get_subtree(int u){
	vi uzy(n);
	vi V;
	V.pb(u);
	uzy[u]=1;
			for(int i=0; i<V.size(); i++){
				int v=V[i];
				for(int uu:E3[v]){
					if(par[uu]==v){
						uzy[uu]=1;
						V.pb(uu);
					}
				}
			}
	int t=V.size();
			for(int i=0; i<t; i++){
				int v=V[i];
				for(int uu:kto[v]){
					//deb(uu);
					if(!uzy[uu]){
						V.pb(uu);
						uzy[uu]=1;
					}
				}
			}
	return V;
}
void dfs2(int v){
	lo[v]=pre[v]=wsk++;
	for(int u:E2[v]){
		if(!pre[u]){
			par[u]=v;
			dfs2(u);
			lo[v]=min(lo[v], lo[u]);
		}
		else if(u!=par[v]){
			lo[v]=min(lo[v], pre[u]);
		}
	}
	if(par[v]!=-1 && lo[v]>=pre[par[v]]){
		czy_art[par[v]]=1;
	}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> uu, vector<int> vv) {
	n=_n;
	for(int i=0; i<uu.size(); i++){
		E[uu[i]].pb(vv[i]);
		E[vv[i]].pb(uu[i]);
	}
	par[0]=-1;
	dfs(0);
	int ile=0;
	for(int u:E[0]){
		if(par[u]==0)ile++;
	}
	czy_art[0]=(ile!=1);
	for(int i=0; i<n; i++){
		//deb(i, par[i], czy_art[i]);
	}
	color(0, 0);
	for(int i=0; i<n; i++){
		pre[i]=0;
		for(int j:E[i]){
			if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]);
		}
		//deb(i, bcc[i]);
	}
	for(int i=0; i<n; i++){
		if(!czy_root[i])continue;
		sort(all(E2[i]));
		E2[i].resize(unique(all(E2[i]))-E2[i].begin());
		//deb(i, E2[i].size());
		for(int u:E2[i]){
			//deb(u);
		}
	}
	cent=-5;
	dfs_cent(0);
	par[cent]=-1;
	dfs_sz(cent);
	deb(cent);
	for(int i=0; i<n; i++){
		if(czy_root[i]){
			//deb(i, roz[i], siz[i])
		}
	}
	int A=min({a, b, c}), C=max({a, b, c});
	int B=n-A-C;
	bool bb=0;
	vector<int> res(n, 0);
	vi X,Y,Z;
	for(int u:E3[cent]){
		if(siz[u]>=A){
			//assert(siz[u]*2<=n);
			//assert(n-siz[u]>=B);
			deb(u, siz[u], A);
			vi V=get_subtree(u);
			//assert(n<=5000);
			vi dozw(n);
			for(int i:V){
				dozw[i]=1;
			}
			X=find(A, dozw);
			//assert(X.size()==A);
			for(int i:X){
				//deb(i);
			}
			for(int &i:dozw)i^=1;
			Y=find(B, dozw);
			//assert(Y.size()==B);
			for(int &i:dozw)i=0;
			for(int i:Y){
				dozw[i]=1;
			}
			for(int i:X){
				dozw[i]=1;
			}
			for(int i=0; i<n; i++){
				if(!dozw[i])Z.pb(i);
			}
			bb=1;
			break;
		}
	}
	deb("a");
	if(!bb){
		if(roz[0]==1)return res;
		//if(n>=5000)assert(false);
		for(int u:E3[cent]){
			roz[u]=siz[u];
			czy_root[u]=1;
			kto[u]=get_subtree(u);
			assert(siz[u]==kto[u].size());
			roz[u]=siz[u];
			for(int v:kto[u])bcc[v]=u, czy_root[v]=0;
		}
		for(int u:kto[0]){
			if(u!=0){
				kto[u]={u};
				bcc[u]=u;
				roz[u]=1;
				czy_root[u]=1;
			}
		}
		kto[0]={0};
		roz[0]=1;
		for(int i=0; i<n; i++)E2[i].clear();
		for(int i=0; i<n; i++){
			pre[i]=0;
			for(int j:E[i]){
				if(bcc[i]!=bcc[j])E2[bcc[i]].pb(bcc[j]);
			}
			//deb(i, bcc[i]);
		}
		for(int i=0; i<n; i++){
			if(!czy_root[i])continue;
			sort(all(E2[i]));
			E2[i].resize(unique(all(E2[i]))-E2[i].begin());
		}
		for(int i=0; i<n; i++){
			//deb(i, bcc[i], czy_root[i], kto[i].size(), E2[i].size())
			if(czy_root[i]){
				for(int u:E2[i]){
					//deb(u);
				}
			}
		}
		vi V;
		for(int i=0; i<n; i++){
			if(czy_root[i])V.pb(i);
		}
		vi czy_cand(V.size(), 1);
		vi mamy;
		vi cand;
		int sum=0;
		cand.pb(0);
		czy_cand[0]=0;
		//assert(A==1);
		while(sum<A){
			for(int i:V)pre[i]=0, czy_art[i]=0;
			for(int i:mamy)pre[i]=1e9;
			wsk=1;
			bb=0;
			for(int i:V){
				if(!pre[i]){
					par[i]=-1;
					dfs2(i);
					bb=1;
					break;
				}
			}
			assert(bb);
			bb=0;
			ile=0;
			for(int u:E[0]){
				if(par[u]==0)ile++;
			}
			czy_art[0]=(ile!=1);
			for(int &i:cand){
				if(!czy_art[i]){
					mamy.pb(i);
					sum+=roz[i];
					for(int u:E2[i]){
						if(czy_cand[u]){
							czy_cand[u]=0;
							cand.pb(u);
						}
					}
					bb=1;
					swap(i, cand.back());
					cand.pp();
					break;
				}
			}
			assert(bb);
		}
		//assert(mamy.size()==1);
		vi dozw(n);
		for(int i:mamy){
			for(int j:kto[i]){
				dozw[j]=1;
			}
		}
			//X=find(A, dozw);
			for(int i:X){
				//deb(i);
			}
			for(int &i:dozw)i^=1;
			Y=find(B, dozw);
			for(int &i:dozw)i=0;
			for(int i:Y){
				dozw[i]=1;
			}
			for(int i:X){
				dozw[i]=1;
			}
			for(int i=0; i<n; i++){
				if(!dozw[i])Z.pb(i);
			}
	}
	if(A!=a){
		swap(A, B);
		swap(X, Y);
	}
	if(A!=a){
		swap(A, C);
		swap(X, Z);
	}
	if(B!=b){
		swap(C, B);
		swap(Z, Y);
	}
	for(int i:X)res[i]=1;
	for(int i:Y)res[i]=2;
	for(int i:Z)res[i]=3;
	
	return res;
}

Compilation message (stderr)

split.cpp: In function 'vi find(int, vi)':
split.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
split.cpp: In function 'vi get_subtree(int)':
split.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    for(int i=0; i<V.size(); i++){
      |                 ~^~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:163:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |  for(int i=0; i<uu.size(); i++){
      |               ~^~~~~~~~~~
split.cpp:190:11: warning: unused variable 'u' [-Wunused-variable]
  190 |   for(int u:E2[i]){
      |           ^
split.cpp:222:12: warning: unused variable 'i' [-Wunused-variable]
  222 |    for(int i:X){
      |            ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp:250:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |    assert(siz[u]==kto[u].size());
      |           ~~~~~~^~~~~~~~~~~~~~~
split.cpp:280:13: warning: unused variable 'u' [-Wunused-variable]
  280 |     for(int u:E2[i]){
      |             ^
split.cpp:342:12: warning: unused variable 'i' [-Wunused-variable]
  342 |    for(int i:X){
      |            ^

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