제출 #105398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105398		luciocf	이상적인 도시 (IOI12_city)	C++14	55 / 100	163 ms	5112 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];
vector<int> grafo[maxn];

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

void bfs(int u)
{
	queue<int> fila;

	dist[u] = 0, fila.push(u);

	while (!fila.empty())
	{
		int u = fila.front();
		fila.pop();

		for (auto v: grafo[u])
			if (dist[v] == -1)
				dist[v] = dist[u]+1, fila.push(v);
	}
}

int solve_small(void)
{
	int ans = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (j == i) continue;

			if (abs(x[i]-x[j])+abs(y[i]-y[j]) == 1)
				grafo[i].push_back(j);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		memset(dist, -1, sizeof dist);

		bfs(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: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45