oj.uz

Submission #253420

# Submission time Handle Problem Language Result Execution time Memory
253420 2020-07-28T03:57:42 Z tinjyu Ideal city (IOI12_city) C++14
0 / 100
 11 ms 12416 KB 
#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]);
	}
	for(int i=0;i<n;i++)
	{
		x[i]-=mix;
		y[i]-=miy;
		map[x[i]][y[i]]=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<=4;i++)
		{
			ans+=now*sumx[i];
			num+=sumx[i];
			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;
	}
	
	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -