oj.uz

Submission #116517

# Submission time Handle Problem Language Result Execution time Memory
116517 2019-06-12T16:38:57 Z faustaadp Ideal city (IOI12_city) C++17
55 / 100
 215 ms 6776 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 11 ms 3584 KB Output is correct
5 Correct 9 ms 3584 KB Output is correct
6 Correct 13 ms 3456 KB Output is correct
7 Correct 19 ms 3456 KB Output is correct
8 Correct 13 ms 3584 KB Output is correct
9 Correct 14 ms 3584 KB Output is correct
10 Correct 13 ms 3584 KB Output is correct
11 Correct 13 ms 3584 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3584 KB Output is correct
2 Correct 73 ms 3608 KB Output is correct
3 Correct 142 ms 3684 KB Output is correct
4 Correct 134 ms 3648 KB Output is correct
5 Correct 199 ms 3712 KB Output is correct
6 Correct 210 ms 3704 KB Output is correct
7 Correct 211 ms 3832 KB Output is correct
8 Correct 215 ms 3712 KB Output is correct
9 Correct 209 ms 3692 KB Output is correct
10 Correct 202 ms 3692 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 10 ms 3584 KB Output is correct
3 Correct 20 ms 4728 KB Output is correct
4 Correct 20 ms 4736 KB Output is correct
5 Correct 37 ms 6648 KB Output is correct
6 Correct 38 ms 6648 KB Output is correct
7 Correct 38 ms 6776 KB Output is correct
8 Correct 35 ms 6648 KB Output is correct
9 Correct 35 ms 6584 KB Output is correct
10 Correct 36 ms 6676 KB Output is correct

Subtask #4
0 / 45.0

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