Submission #133452

#	Time	Username	Problem	Language	Result	Execution time	Memory
133452		bogdan10bos	Ideal city (IOI12_city)	C++14	100 / 100	342 ms	18160 KiB

city

/// Bravo Bodo plm
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int mod = int(1e9);

int N, ans;

void solve(int *X, int *Y)
{
	map<pii, int> mp;
	vector<pii> v;
	for(int i = 0; i < N; i++)	v.push_back({X[i], Y[i]});
	sort(begin(v), end(v));

	vector<int> g(N);
	int G = 1;
	g[0] = 0;
	for(int i = 1; i < N; i++)
	{
		if(v[i].first == v[i - 1].first && v[i].second == v[i - 1].second + 1)
			g[i] = g[i - 1];
		else
			g[i] = G++;
	}

	vector< vector<int> > edg(G);
	vector<int> val(G);

	for(int i = 0; i < N; i++)
	{
		mp[ v[i] ] = g[i];
		val[ g[i] ]++;
	}

	map<pii, int> hasEdge;
	for(int i = 0; i < N; i++)
	{
		int x = v[i].first, y = v[i].second, z = g[i];

		auto addEdge = [&](int x, int y)
		{
			if(hasEdge.count({x, y}))	return;
			hasEdge[{x, y}] = hasEdge[{y, x}] = 1;
			edg[x].push_back(y);
			edg[y].push_back(x);
		};

		if(mp.count({x - 1, y}))
			addEdge(z, mp[{x - 1, y}]);
		if(mp.count({x + 1, y}))
			addEdge(z, mp[{x + 1, y}]);
	}

	vector<int> sz(G);
	function<void(int, int)> DFS = [&](int nod, int fth)
	{
		sz[nod] = val[nod];
		for(auto nxt: edg[nod])
			if(nxt != fth)
			{
				DFS(nxt, nod);
				sz[nod] += sz[nxt];
			}
	};
	DFS(0, -1);

	int tot = sz[0];
	for(int i = 0; i < G; i++)
	{
		ans += (1LL * sz[i] * (tot - sz[i])) % mod;
		if(ans >= mod)	ans -= mod;
	}
}

int DistanceSum(int _N, int *X, int *Y)
{
	N = _N, ans = 0;
	solve(X, Y);
	solve(Y, X);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45