Submission #116517

#	Time	Username	Problem	Language	Result	Execution time	Memory
116517		faustaadp	Ideal city (IOI12_city)	C++17	55 / 100	215 ms	6776 KiB

city

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,has,mo=1e9,j;
ll x[101010];
ll y[101010];
ll p[101010];
ll jar[101010];
vector<ll> v[101010];
int DistanceSum(int N, int *X, int *Y) 
{
	for(i=0;i<N;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
	//	cout<<x[i]<<" "<<y[i]<<"\n";
	}
	if(N<=2000)
	{
		for(i=0;i<N;i++)
			for(j=0;j<N;j++)
				if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
				{
		//			cout<<i<<" _ "<<j<<"\n";
					v[i].pb(j);
				}
		for(i=0;i<N;i++)
		{
			memset(jar,-1,sizeof(jar));
			queue<ll> q;
			q.push(i);
			jar[i]=0;
			while(!q.empty())
			{
				ll u=q.front();
				q.pop();
				for(j=0;j<v[u].size();j++)
					if(jar[v[u][j]]==-1)
					{
						jar[v[u][j]]=jar[u]+1;
						q.push(v[u][j]);
					}
			}
			for(j=i;j<N;j++)
			{
			//	cout<<i<<" "<<j<<" "<<jar[j]<<"\n";
				has+=jar[j];
			}
		}
	}
	else 
	{
		sort(x,x+N);
		sort(y,y+N);
		p[0]=x[0];for(i=1;i<N;i++)p[i]=p[i-1]+x[i];
		for(i=0;i<N;i++)
		{
			has+=(p[N-1]-p[i])-(x[i]*(N-i-1));
			has%=mo;
		}
		p[0]=y[0];for(i=1;i<N;i++)p[i]=p[i-1]+y[i];
		for(i=0;i<N;i++)
		{
			has+=(p[N-1]-p[i])-(y[i]*(N-i-1));
			has%=mo;
		}
	}
  	return has%mo;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<v[u].size();j++)
             ~^~~~~~~~~~~~

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