oj.uz

Submission #105395

# Submission time Handle Problem Language Result Execution time Memory
105395 2019-04-11T20:36:47 Z luciocf Ideal city (IOI12_city) C++14
34 / 100
 1000 ms 3576 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 21 ms 768 KB Output is correct
7 Correct 26 ms 768 KB Output is correct
8 Correct 22 ms 768 KB Output is correct
9 Correct 23 ms 768 KB Output is correct
10 Correct 23 ms 868 KB Output is correct
11 Correct 23 ms 896 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 848 KB Output is correct
2 Correct 598 ms 848 KB Output is correct
3 Execution timed out 1075 ms 896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 12 ms 896 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 15 ms 1920 KB Output is correct
5 Correct 41 ms 3508 KB Output is correct
6 Correct 31 ms 3432 KB Output is correct
7 Correct 33 ms 3576 KB Output is correct
8 Correct 31 ms 3448 KB Output is correct
9 Correct 30 ms 3388 KB Output is correct
10 Correct 30 ms 3448 KB Output is correct

Subtask #4
0 / 45.0

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