oj.uz

Submission #823278

# Submission time Handle Problem Language Result Execution time Memory
823278 2023-08-12T10:21:14 Z caganyanmaz Ideal city (IOI12_city) C++17
32 / 100
 48 ms 1996 KB 
#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
#define mp(x...) array<int, 2>({x})
using namespace std;

constexpr static int MOD = 1e9;
static inline int add(int a, int b) { return (a+b) % MOD; }
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }

constexpr static int MXN = 2000;
int32_t n, *x, *y;
vector<int> g[MXN];
vector<array<int, 2>> nodes;

int find(int a, int b)
{
	auto it = lower_bound(nodes.begin(), nodes.end(), mp(a, b));
	if (it != nodes.end() && (*it)[0] == a && (*it)[1] == b)
		return it - nodes.begin();
	return -1;
}

void try_insert(int node, int a, int b)
{
	int res = find(a, b);
	if (res != -1)
		g[node].pb(res);
}

int dist[MXN];
int bfs(int root)
{
	for (int i = 0; i < n; i++)
		dist[i] = -1;
	queue<int> q;
	dist[root] = 0;
	q.push(root);
	int res = 0;
	while (q.size())
	{
		int node = q.front();
		q.pop();
		res += dist[node];
		for (int c : g[node])
		{
			if (dist[c] == -1)
			{
				dist[c] = dist[node]+1;
				q.push(c);
			}
		}
	}
	return res;
}

int32_t DistanceSum(int32_t N, int32_t *X, int32_t *Y) 
{
	x = X, y = Y;
	n = N;
	for (int i = 0; i < n; i++)
		nodes.pb(mp(x[i], y[i]));
	sort(nodes.begin(), nodes.end());
	for (int i = 0; i < n; i++)
	{
		auto [x, y] = nodes[i];
		try_insert(i, x+1, y);
		try_insert(i, x-1, y);
		try_insert(i, x, y+1);
		try_insert(i, x, y-1);
	}
	int res = 0;
	for (int i = 0; i < n; i++)
		res += bfs(i);
	return (res / 2) % MOD;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 432 KB Output is correct
2 Correct 11 ms 340 KB Output is correct
3 Correct 24 ms 484 KB Output is correct
4 Correct 26 ms 468 KB Output is correct
5 Correct 45 ms 496 KB Output is correct
6 Correct 40 ms 468 KB Output is correct
7 Correct 48 ms 468 KB Output is correct
8 Correct 38 ms 508 KB Output is correct
9 Correct 41 ms 512 KB Output is correct
10 Correct 36 ms 468 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -