oj.uz

Submission #986350

# Submission time Handle Problem Language Result Execution time Memory
986350 2024-05-20T11:08:54 Z Pyqe Ideal city (IOI12_city) C++17
100 / 100
 145 ms 32392 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 3 ms 21136 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 4 ms 20916 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 4 ms 21120 KB Output is correct
10 Correct 3 ms 21336 KB Output is correct
11 Correct 3 ms 21084 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21080 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 5 ms 21080 KB Output is correct
7 Correct 5 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21148 KB Output is correct
10 Correct 5 ms 21080 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24864 KB Output is correct
2 Correct 14 ms 24532 KB Output is correct
3 Correct 32 ms 26920 KB Output is correct
4 Correct 28 ms 26536 KB Output is correct
5 Correct 66 ms 31828 KB Output is correct
6 Correct 57 ms 31060 KB Output is correct
7 Correct 65 ms 31208 KB Output is correct
8 Correct 63 ms 32392 KB Output is correct
9 Correct 60 ms 30388 KB Output is correct
10 Correct 48 ms 30280 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24412 KB Output is correct
2 Correct 21 ms 24728 KB Output is correct
3 Correct 64 ms 26532 KB Output is correct
4 Correct 62 ms 26960 KB Output is correct
5 Correct 145 ms 30416 KB Output is correct
6 Correct 109 ms 31416 KB Output is correct
7 Correct 133 ms 30508 KB Output is correct
8 Correct 102 ms 31180 KB Output is correct
9 Correct 85 ms 31284 KB Output is correct
10 Correct 102 ms 31336 KB Output is correct