Submission #823278

#	Time	Username	Problem	Language	Result	Execution time	Memory
823278		caganyanmaz	Ideal city (IOI12_city)	C++17	32 / 100	48 ms	1996 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45