Submission #147069

#	Time	Username	Problem	Language	Result	Execution time	Memory
147069		dennisstar	Split the Attractions (IOI19_split)	C++17	100 / 100	248 ms	29044 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vim;
vim V[100010], W[100010];
vim C[100010], par;
int chk[100010];
pair<int,int> pi[3];
int N, Ctd;
vim ans;
int chkans[100010];
void mst(int lev)
{
	chk[lev]=1;
	for (int i:V[lev]) {
		if (!chk[i]) {
			par[i]=lev;
			C[lev].push_back(i);
			mst(i);
		}
	}
}
int cent(int lev)
{
	vector<int> Cs;
	for (int i:C[lev]) {
		Cs.push_back(cent(i));
	}
	int ret=0, flag=0;
	for (int i:Cs) {
		ret+=i;
		if (i>N/2) flag=1;
	}
	if (N-ret-1>N/2) flag=1;
	if (!flag) Ctd=lev;
	return ret+1;
}
void dfs(int lev) 
{
	chk[lev]=1;
	for (int i:C[lev]) {
		if (!chk[i]) {
			W[lev].push_back(i);
			W[i].push_back(lev);
			dfs(i);
		}
	}
	if (!chk[par[lev]]) {
		W[lev].push_back(par[lev]);
		W[par[lev]].push_back(lev);
		dfs(par[lev]);
	}
}
int gC(int lev){
	chk[lev]=1;
	int ret=0;
	for (int i:W[lev]) {
		if (!chk[i]) ret+=gC(i);
	}
	return ret+1;
}
void GA1(int st, int sw)
{
	if (sw==0) {
		if (!pi[0].first) return ;
		chk[st]=1;
		chkans[st]=pi[0].second+1;
		pi[0].first--;
		for (int i:W[st]) {
			if (!chk[i]) {
				GA1(i, sw);
			}
		}
	}
	if (sw==1) {
		if (!pi[1].first) return ;
		chk[st]=1;
		chkans[st]=pi[1].second+1;
		pi[1].first--;
		for (int i:W[st]) {
			if (!chk[i]) {
				GA1(i, sw);
			}
		}
	}
	if (sw==2) {
		for (int i=0; i<N; i++) if (!chkans[i]) chkans[i]=pi[2].second+1;
		for (int i=0; i<N; i++) ans.push_back(chkans[i]);
	}
}
int dfs1(int lev)
{
	chk[lev]=1;
	int ret=1;
	for (int i:V[lev]) {
		if (!chk[i]) {
			ret+=dfs1(i);
		}
	}
	return ret;
}
void dfs2(int lev)
{
	if (!pi[0].first) return ;
	chk[lev]=1;
	chkans[lev]=pi[0].second;
	pi[0].first--;
	for (int i:V[lev]) {
		if (!chk[i]&&i!=Ctd) dfs2(i);
	}
}
void dfs3(int lev)
{
	if (!pi[1].first) return ;
	chk[lev]=1;
	chkans[lev]=pi[1].second;
	pi[1].first--;
	for (int i:V[lev]) {
		if (!chk[i]) dfs3(i);
	}
}
void dfs4()
{
	int i, j=0;
	for (i=0; i<N; i++) {if (!chk[i]) {chkans[i]=pi[2].second; j++;}}
	for (i=0; i<N; i++) ans.push_back(chkans[i]+1);
	if (j!=pi[2].first) {
		printf("%d", 1/0);
	}
}
int GA2()
{
	int i, ret, fl=0;
	memset(chk, 0, sizeof(chk));
	chk[Ctd]=1;
	for (i=0; i<N; i++) {
		if (i!=Ctd&&!chk[i]) {
			ret=dfs1(i);
			if (ret>=pi[0].first) {
				memset(chk, 0, sizeof(chk));
				dfs2(i);
				dfs3(Ctd);
				dfs4();
				fl=1;
				break;
			}
		}
	}
	if (!fl) return -1;
	return 0;
}
vim IMPOSSIBLE()
{
	vim ret;
	for (int i=0; i<N; i++) ret.push_back(0);
	//if (ret.size()!=N) assert(false);
	return ret;
}

vim find_split(int n, int a, int b, int c, vim p, vim q) {
	N=n;
	par.resize(n);
	pi[0]={a,0}; pi[1]={b,1}; pi[2]={c,2};
	sort(pi,pi+3);
	int i;
	for (i=0; i<p.size(); i++) {
		V[p[i]].push_back(q[i]);
		V[q[i]].push_back(p[i]);
	}
	mst(0);
	cent(0);
	memset(chk, 0, sizeof(chk));
	dfs(Ctd);
	memset(chk, 0, sizeof(chk));
	chk[Ctd]=1;
	vim CtdV;
	for (int j:W[Ctd]) CtdV.push_back(gC(j));
	memset(chk, 0, sizeof(chk));
	chk[Ctd]=1;
	for (i=0; i<CtdV.size(); i++) {
		if (CtdV[i]>=pi[0].first){
			GA1(W[Ctd][i], 0);
			GA1(Ctd, 1);
			GA1(0, 2);
			if (ans.size()!=N) assert(false);
			return ans;
		}
	}
	if (GA2()==-1) {
		return IMPOSSIBLE();
	}
	else {
		//if (ans.size()!=N) assert(false);
		return ans;
	}
}

Compilation message (stderr)

split.cpp: In function 'void dfs4()':
split.cpp:128:17: warning: division by zero [-Wdiv-by-zero]
   printf("%d", 1/0);
                ~^~
split.cpp: In function 'vim find_split(int, int, int, int, vim, vim)':
split.cpp:166:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<p.size(); i++) {
            ~^~~~~~~~~
split.cpp:180:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0; i<CtdV.size(); i++) {
            ~^~~~~~~~~~~~
split.cpp:185:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ans.size()!=N) assert(false);
        ~~~~~~~~~~^~~

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