oj.uz

Submission #105398

# Submission time Handle Problem Language Result Execution time Memory
105398 2019-04-11T20:44:36 Z luciocf Ideal city (IOI12_city) C++14
55 / 100
 163 ms 5112 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];
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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3196 KB Output is correct
2 Correct 51 ms 3072 KB Output is correct
3 Correct 99 ms 3184 KB Output is correct
4 Correct 99 ms 3072 KB Output is correct
5 Correct 157 ms 3320 KB Output is correct
6 Correct 153 ms 3200 KB Output is correct
7 Correct 157 ms 3200 KB Output is correct
8 Correct 159 ms 3320 KB Output is correct
9 Correct 163 ms 3216 KB Output is correct
10 Correct 154 ms 3264 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3200 KB Output is correct
2 Correct 10 ms 3200 KB Output is correct
3 Correct 18 ms 3884 KB Output is correct
4 Correct 18 ms 3960 KB Output is correct
5 Correct 33 ms 5112 KB Output is correct
6 Correct 44 ms 5100 KB Output is correct
7 Correct 35 ms 5092 KB Output is correct
8 Correct 31 ms 5112 KB Output is correct
9 Correct 32 ms 5112 KB Output is correct
10 Correct 55 ms 5112 KB Output is correct

Subtask #4
0 / 45.0

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