Submission #105395

#	Time	Username	Problem	Language	Result	Execution time	Memory
105395		luciocf	Ideal city (IOI12_city)	C++14	34 / 100	1075 ms	3576 KiB

city

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int mod = 1e9;

typedef pair<int, int> pii;

int n;
int x[maxn], y[maxn];

int prefX[maxn], prefY[maxn];

// -------- BFS STUFF --------
int dist[maxn];

int linha[] = {-1, 1, 0, 0};
int coluna[] = {0, 0, -1, 1};
// ---------------------------

map<pii, int> ind;

void bfs(int x, int y)
{
	queue<pii> fila;

	dist[ind[{x, y}]] = 0, fila.push({x, y});

	while (!fila.empty())
	{
		int x = fila.front().first, y = fila.front().second;
		fila.pop();

		int u = ind[{x, y}];

		for (int i = 0; i < 4; i++)
		{
			int a = x+linha[i], b = y+coluna[i];
			if (ind.find({a, b}) == ind.end() || dist[ind[{a, b}]] != -1) continue;

			dist[ind[{a, b}]] = dist[u]+1, fila.push({a, b});
		}
	}
}

int solve_small(void)
{
	int ans = 0;

	for (int i = 1; i <= n; i++)
		ind[{x[i], y[i]}] = i;

	for (int i = 1; i <= n; i++)
	{
		memset(dist, -1, sizeof dist);
		bfs(x[i], y[i]);

		for (int j = 1; j < i; j++)
			ans = (ans+dist[j])%mod;
	}

	return ans;
}

int DistanceSum(int N, int *X, int *Y)
{
	n = N;
	for (int i = 1; i <= n; i++) 
		x[i] = X[i-1], y[i] = Y[i-1];

	if (n <= 2000) return solve_small();
	
	sort(x+1, x+n+1); sort(y+1, y+n+1);

	for (int i = 1; i <= n; i++)
	{
		prefX[i] = (prefX[i-1] + x[i])%mod;
		prefY[i] = (prefY[i-1] + y[i])%mod;
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		long long soma = (1ll*(i-1)*x[i] - 1ll*prefX[i-1] + 1ll*mod)%mod;
		ans = (ans+soma)%mod;

		soma = (1ll*(i-1)*y[i] - 1ll*prefY[i-1] + 1ll*mod)%mod;
		ans = (ans+soma)%mod;
	}

	return ans;
}

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