oj.uz

답안 #133452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133452 2019-07-20T17:44:37 Z bogdan10bos 이상적인 도시 (IOI12_city) C++14
100 / 100
 342 ms 18160 KB 
/// 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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 540 KB Output is correct
4 Correct 5 ms 580 KB Output is correct
5 Correct 6 ms 636 KB Output is correct
6 Correct 6 ms 560 KB Output is correct
7 Correct 6 ms 720 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 5 ms 564 KB Output is correct
10 Correct 5 ms 632 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 2292 KB Output is correct
2 Correct 44 ms 2340 KB Output is correct
3 Correct 129 ms 5012 KB Output is correct
4 Correct 126 ms 5128 KB Output is correct
5 Correct 267 ms 9732 KB Output is correct
6 Correct 264 ms 9812 KB Output is correct
7 Correct 271 ms 10196 KB Output is correct
8 Correct 268 ms 9604 KB Output is correct
9 Correct 264 ms 10224 KB Output is correct
10 Correct 298 ms 18160 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 3700 KB Output is correct
2 Correct 52 ms 3236 KB Output is correct
3 Correct 153 ms 8728 KB Output is correct
4 Correct 143 ms 7284 KB Output is correct
5 Correct 342 ms 16932 KB Output is correct
6 Correct 298 ms 12548 KB Output is correct
7 Correct 327 ms 17288 KB Output is correct
8 Correct 306 ms 12884 KB Output is correct
9 Correct 299 ms 11844 KB Output is correct
10 Correct 290 ms 11528 KB Output is correct