Submission #253418

#	Time	Username	Problem	Language	Result	Execution time	Memory
253418		tinjyu	Ideal city (IOI12_city)	C++14	32 / 100	226 ms	32384 KiB

city

#include <iostream>
using namespace std;
long long int sumx[100005],sumy[100005],t[100005],len[100005],n,map[2005][2005],tag[2005][2005];
int DistanceSum(int N, int *x, int *y) {
	n=N;
	int mix=2000000000,miy=2000000000;
	for(int i=0;i<n;i++)
	{
		mix=min(mix,x[i]);
		miy=min(miy,y[i]);
	}
	if(n>2000)
	{
		long long int ans=0;
		for(int i=0;i<n;i++)
		{
			sumx[x[i]]++;
			sumy[y[i]]++;
		}
		long long int now=0,num=0;
		for(int i=0;i<=100000;i++)
		{
			//cout<<sumx[i]<<" "<<now<<" "<<ans<<endl;
			ans+=now*sumx[i];
			num+=sumx[i];
			now+=now+num;
			now%=1000000000;
			ans%=1000000000;
		}
		now=0,num=0;
		for(int i=0;i<=100000;i++)
		{
			ans+=now*sumy[i];
			num+=sumy[i];
			now+=num;
			now%=1000000000;
			ans%=1000000000;
		}
		return ans;
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)map[i][j]=-1;
	}
	for(int i=0;i<n;i++)
	{
		x[i]-=mix;
		y[i]-=miy;
		map[x[i]][y[i]]=i;
	}
	long long int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			tag[x[j]][y[j]]=0;
		}
		t[0]=i;
		len[0]=0;
		tag[x[i]][y[i]]=1;
		long long int p=0,pp=0;
		while(p<=pp)
		{
			if(t[p]<i)ans+=len[p];
			ans%=1000000000;
			for(int i=1;i<=4;i++)
			{
				long long int tmpx=x[t[p]],tmpy=y[t[p]];
				if(i==1)tmpx++;
				if(i==2)tmpy++;
				if(i==3)tmpx--;
				if(i==4)tmpy--;
				if(tmpx>=0 && tmpy>=0 && map[tmpx][tmpy]!=-1 && tag[tmpx][tmpy]==0)
				{
					pp++;
					len[pp]=len[p]+1;
					t[pp]=map[tmpx][tmpy];
					tag[tmpx][tmpy]=1;
				}
			}
			p++;		
		}
	}
  return ans;

}

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