Submission #986403

#	Time	Username	Problem	Language	Result	Execution time	Memory
986403		Pyqe	Split the Attractions (IOI19_split)	C++17	100 / 100	364 ms	86728 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,ttl=0,nn=0,dsu[200069],dh[100069],pg[100069],sbt[300069],wg[100069],pr[100069],fh[100069],ca[100069],sq[100069];
pair<long long,long long> d[3],mdh[100069];
vector<pair<long long,long long>> al[100069];
bitset<300069> vtd;
bitset<100069> vtd2,spc;
vector<long long> al2[300069],sbl[300069],al3[100069];
multiset<long long> ms[100069];
bool bad=0,r0=0;

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void bct(long long x,long long b4)
{
	long long i,sz=al[x].size(),l,p;
	
	vtd[x]=1;
	vtd2[x]=1;
	mdh[x]={dh[x],-1};
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(p==b4)
		{
			continue;
		}
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			pg[x]=p;
			bct(l,p);
		}
		if(vtd2[l])
		{
			dsu[fd(p)]=fd(pg[l]);
			mdh[x]=min(mdh[x],{dh[l],p});
		}
		else if(mdh[l].fr<=dh[x])
		{
			dsu[fd(p)]=fd(mdh[l].sc);
			mdh[x]=min(mdh[x],{mdh[l].fr,p});
		}
	}
	vtd2[x]=0;
}

void bd(long long x)
{
	long long i,sz=al2[x].size(),l,e=-1;
	
	vtd[x]=1;
	sbt[x]=x<n;
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		if(!vtd[l])
		{
			bd(l);
			sbt[x]+=sbt[l];
		}
		else
		{
			e=l;
		}
	}
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		if(l!=e)
		{
			sbl[x].push_back(sbt[l]);
		}
		else
		{
			sbl[x].push_back(n-sbt[x]);
		}
	}
}

void trv(long long x,long long xx)
{
	long long i,sz=al[x].size(),l;
	
	vtd[x]=1;
	if(d[xx].fr)
	{
		sq[x]=d[xx].sc;
		d[xx].fr--;
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		if((!wg[l]||spc[l]==spc[x])&&!vtd[l])
		{
			trv(l,xx);
		}
	}
}

void dbd(long long x,long long b4)
{
	long long i,sz=al[x].size(),l,p,mn=dh[x];
	
	vtd[x]=1;
	vtd2[x]=1;
	fh[x]=dh[x];
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(p==b4)
		{
			continue;
		}
		if(wg[l])
		{
			if(!vtd[l])
			{
				dh[l]=dh[x]+1;
				pr[l]=x;
				dbd(l,p);
				fh[x]=min(fh[x],fh[l]);
				al3[x].push_back(l);
				ms[x].insert(fh[l]);
			}
			else if(vtd2[l])
			{
				fh[x]=min(fh[x],dh[l]);
				al3[l].push_back(x);
				mn=min(mn,dh[l]);
			}
		}
	}
	vtd2[x]=0;
	ms[x].insert(mn);
}

bool cmp(long long x,long long y)
{
	return dh[x]>dh[y];
}

void dtrv(long long x)
{
	long long i,sz=al3[x].size(),l;
	
	vtd[x]=1;
	ttl+=wg[x];
	spc[x]=1;
	if(ttl>=d[0].fr)
	{
		r0=1;
		return;
	}
	nn++;
	ca[nn]=x;
	sort(al3[x].begin(),al3[x].end(),cmp);
	for(i=0;i<sz;i++)
	{
		l=al3[x][i];
		if(!vtd[l]&&(fh[l]>=dh[x]||dh[l]==dh[x]+1))
		{
			dtrv(l);
			if(r0)
			{
				return;
			}
		}
	}
	nn--;
	if(pr[x]+1)
	{
		ms[pr[x]].erase(ms[pr[x]].find(fh[x]));
		if(!vtd[pr[x]]&&(!nn||*ms[pr[x]].begin()>dh[ca[nn]]))
		{
			dtrv(pr[x]);
		}
	}
}

vector<int> find_split(int on,int od,int od2,int od3,vector<int> ka,vector<int> la)
{
	long long i,j,ii,l,w,sz,p,e;
	vector<long long> v;
	vector<int> v2;
	
	n=on;
	d[0]={od,1};
	d[1]={od2,2};
	d[2]={od3,3};
	sort(d,d+3);
	m=ka.size();
	for(i=0;i<m;i++)
	{
		al[ka[i]].push_back({la[i],i});
		al[la[i]].push_back({ka[i],i});
		dsu[i]=i;
	}
	bct(0,-1);
	for(i=0;i<m;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			al2[ka[i]].push_back(n+fd(i));
			al2[n+fd(i)].push_back(ka[i]);
			swap(ka[i],la[i]);
		}
	}
	for(i=0;i<n+m;i++)
	{
		sort(al2[i].begin(),al2[i].end());
		v.clear();
		sz=al2[i].size();
		for(j=0;j<sz;j++)
		{
			l=al2[i][j];
			if(!j||l!=al2[i][j-1])
			{
				v.push_back(l);
			}
		}
		al2[i]=v;
	}
	vtd.reset();
	bd(0);
	for(i=n;i<n+m;i++)
	{
		sz=al2[i].size();
		for(j=0;j<sz;j++)
		{
			l=al2[i][j];
			w=sbl[i][j];
			for(ii=0;ii<2;ii++)
			{
				if(w>=d[ii].fr&&n-w>=d[!ii].fr)
				{
					p=l;
					e=ii;
					break;
				}
			}
			if(ii<2)
			{
				break;
			}
		}
		if(j<sz)
		{
			vtd.reset();
			for(j=0;j<sz;j++)
			{
				l=al2[i][j];
				vtd[l]=l!=p;
			}
			trv(p,e);
			vtd.reset();
			vtd[p]=1;
			trv(al2[i][al2[i][0]==p],!e);
			bad=1;
			break;
		}
	}
	if(!bad)
	{
		for(i=n;i<n+m;i++)
		{
			if(fd(i-n)==i-n)
			{
				sz=al2[i].size();
				for(j=0;j<sz;j++)
				{
					w=sbl[i][j];
					if(n-w<d[1].fr)
					{
						break;
					}
				}
				if(j>=sz)
				{
					for(j=0;j<sz;j++)
					{
						l=al2[i][j];
						w=sbl[i][j];
						wg[l]=w;
					}
					vtd.reset();
					dh[l]=0;
					pr[l]=-1;
					dbd(l,-1);
					vtd.reset();
					dtrv(al3[l][al3[l].size()-1]);
					e=ttl<d[0].fr||n-ttl<d[1].fr;
					vtd.reset();
					for(ii=0;ii<2;ii++)
					{
						for(j=0;j<sz;j++)
						{
							l=al2[i][j];
							if(spc[l]==!ii)
							{
								trv(l,ii^e);
								break;
							}
						}
					}
					bad=1;
					break;
				}
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(bad&&!sq[i])
		{
			sq[i]=d[2].sc;
		}
		v2.push_back(sq[i]);
	}
	return v2;
}

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