제출 #116515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116515		faustaadp	Ideal city (IOI12_city)	C++17	0 / 100	1070 ms	5076 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(1)
	{
		for(i=0;i<N;i++)
			for(j=0;j<N;j++)
				if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
					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[v[u][j]]+1;
						q.push(v[u][j]);
					}
			}
			for(j=0;j<N;j++)
				has+=jar[j];
		}
	}
	if(1)
	{
		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));
		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));
	}
  	return has%mo;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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