Submission #986350

#	Time	Username	Problem	Language	Result	Execution time	Memory
986350		Pyqe	Ideal city (IOI12_city)	C++17	100 / 100	145 ms	32392 KiB

city

#include <bits/stdc++.h>

using namespace std;

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

const long long dv=1e9,inf=1e18;
long long nv=0,cr,ctd,al[100069][4],vi[100069],pr[100069],cc[100069],sbt[100069],nr[100069],sr[100069],wg[2][100069],ps[2][100069],fh[2][2][100069],z=0;
pair<pair<long long,long long>,long long> as[2][100069];
vector<long long> vl[100069],al2[100069];
queue<long long> q;

void fpr(long long x)
{
	long long l=al[x][3];
	
	vi[x]=nv;
	if(l)
	{
		if(vi[l]<nv)
		{
			fpr(l);
		}
		pr[x]=pr[l];
	}
	else
	{
		pr[x]=x;
	}
	vl[pr[x]].push_back(x);
	cc[pr[x]]++;
}

void bd(long long x)
{
	long long i,sz=al2[x].size(),l;
	
	vi[x]=nv;
	sbt[x]=cc[x];
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		if(vi[l]<nv)
		{
			bd(l);
			sbt[x]+=sbt[l];
		}
	}
}

void bd2(long long x)
{
	long long i,sz=al2[x].size(),l,mx=sbt[cr]-sbt[x];
	
	vi[x]=nv;
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		if(vi[l]<nv)
		{
			bd2(l);
			mx=max(mx,sbt[l]);
		}
	}
	if(mx*2<=sbt[cr])
	{
		ctd=x;
	}
}

void cdc(long long x)
{
	long long i,ii,im,k,l,sz,l2;
	
	cr=x;
	nv++;
	bd(x);
	nv++;
	bd2(x);
	nv++;
	sz=vl[ctd].size();
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=sz;i++)
		{
			l=vl[ctd][i-1];
			vi[l]=inf;
			l2=al[l][ii];
			fh[ii][0][i]=i;
			fh[ii][1][i]=i;
			if(l2)
			{
				if(vi[l2]!=inf)
				{
					q.push(l2);
					vi[l2]=nv;
					nr[l2]=1;
					sr[l2]=i;
				}
				if(i-1&&al[vl[ctd][i-2]][ii])
				{
					fh[ii][0][i]=fh[ii][0][i-1];
				}
				if(i<sz&&al[vl[ctd][i]][ii])
				{
					fh[ii][1][i]=i+1;
				}
			}
			wg[ii][i]=0;
			ps[ii][i]=0;
		}
		for(i=sz;i;i--)
		{
			fh[ii][1][i]=fh[ii][1][fh[ii][1][i]];
		}
		for(;!q.empty();)
		{
			k=q.front();
			q.pop();
			wg[ii][sr[k]]+=nr[k];
			ps[ii][sr[k]]++;
			for(im=0;im<4;im++)
			{
				l=al[k][im];
				if(l&&vi[l]<nv)
				{
					q.push(l);
					vi[l]=nv;
					nr[l]=nr[k]+1;
					sr[l]=sr[k];
				}
			}
		}
		for(i=1;i<=sz;i++)
		{
			ps[ii][i]+=ps[ii][i-1];
		}
	}
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=sz;i++)
		{
			z+=wg[ii][i]*(ps[!ii][sz]+ps[ii][sz]-ps[ii][fh[ii][1][i]]+ps[ii][fh[ii][0][i]-1]+sz);
			z+=i*(ps[ii][i]-ps[ii][i-1])*(ps[!ii][i-1]+ps[ii][fh[ii][0][i]-1]+i-1-(ps[!ii][sz]-ps[!ii][i]+ps[ii][sz]-ps[ii][fh[ii][1][i]]+sz-i));
			z+=i*(ps[ii][i-1]-(ps[ii][sz]-ps[ii][i]));
		}
	}
	for(i=1;i<=sz;i++)
	{
		z+=i*(i-1-(sz-i));
	}
	k=ctd;
	sz=al2[k].size();
	for(i=0;i<sz;i++)
	{
		l=al2[k][i];
		if(vi[l]!=inf)
		{
			cdc(l);
		}
	}
}

int DistanceSum(int n,int *ya,int *xa)
{
	long long i,j,ii,im,l,sz,y,x,p,y2,x2,p2;
	vector<long long> v;
	
	for(i=1;i<=n;i++)
	{
		y=ya[i-1];
		x=xa[i-1];
		as[0][i]={{y,x},i};
		as[1][i]={{x,y},i};
	}
	for(ii=0;ii<2;ii++)
	{
		sort(as[ii]+1,as[ii]+n+1);
		for(i=2;i<=n;i++)
		{
			y=as[ii][i].fr.fr;
			x=as[ii][i].fr.sc;
			p=as[ii][i].sc;
			y2=as[ii][i-1].fr.fr;
			x2=as[ii][i-1].fr.sc;
			p2=as[ii][i-1].sc;
			if(y==y2&&x==x2+1)
			{
				al[p2][ii*2]=p;
				al[p][ii*2+1]=p2;
			}
		}
	}
	nv++;
	for(i=1;i<=n;i++)
	{
		if(vi[i]<nv)
		{
			fpr(i);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(im=0;im<4;im++)
		{
			l=al[i][im];
			if(l&&pr[i]!=pr[l])
			{
				al2[pr[i]].push_back(pr[l]);
				al2[pr[l]].push_back(pr[i]);
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(pr[i]==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;
		}
	}
	cdc(pr[1]);
	return z%dv;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45