oj.uz

Submission #532275

# Submission time Handle Problem Language Result Execution time Memory
532275 2022-03-02T16:18:31 Z sidon Ideal city (IOI12_city) C++17
100 / 100
 661 ms 62864 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

const array<int, 2> mv[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

const int Z = 1e5;

int n, s[Z];
map<int, int> toS[Z];
set<int> g[Z], h[Z];

void dfs(int u, int p) {
	for(const int &v : g[u]) if(v != p) {
		dfs(v, u);
		s[u] += toS[u][v] = s[v];
		toS[v][u] = n - s[v];
	}
}

i64 curSum, ans;

void cnt(int u) {
	s[u] = 1;
	ans += curSum;
	for(const int &v : h[u]) if(!s[v]) {
		curSum += i64(n - 2 * toS[u][v]);
		cnt(v);
		curSum -= i64(n - 2 * toS[u][v]);
	}
}

int DistanceSum(int N, int *X, int *Y) {

	map<pair<int, int>, int> cAt;

	int o[N], id[N]; n = N;
	for(int i = 0; i < N; ++i)
		cAt[{X[i], Y[i]}] = (o[i] = i) + 1;

	for(int u = 0; u < N; ++u) {
		for(const auto &[dx, dy] : mv) {
			int v = cAt[{X[u] + dx, Y[u] + dy}] - 1;
			if(v >= 0) h[u].insert(v);
		}
	}

	for(int _ = 0; _ < 2; ++_) {
		if(_) {
			cAt.clear();
			for(int i = 0; i < N; ++i)
				cAt[{X[i], Y[i]}] = i + 1;
		}

		sort(o, o + N, [&](const int &i, const int &j) {
			return Y[i] < Y[j];
		});

		for(const int &u : o) {
			int v = cAt[{X[u], Y[u] - 1}] - 1;
			id[u] = v < 0 ? u : id[v];
		}

		fill(s, s + N, 0);
		fill(g, g + N, set<int> ());

		for(int u = 0; u < N; ++u) {
			++s[id[u]];
			for(const int &v : h[u]) if(id[u] != id[v])
				g[id[u]].insert(id[v]);
		}

		dfs(id[0], id[0]);

		for(int u = 0; u < N; ++u)
			for(const int &v : h[u]) if(id[u] != id[v])
				toS[u][v] = toS[id[u]][id[v]];

		swap(X, Y);
	}

	queue<pair<int, int>> q;
	bool vis[N] {1};
	q.emplace(0, 0);

	while(!empty(q)) {
		auto [u, d] = q.front(); q.pop();
		curSum += i64(d);

		for(const int &v : h[u])
			if(v >= 0 && !vis[v])
				vis[v] = 1, q.emplace(v, d + 1);
	}

	fill(s, s + N, 0);
	cnt(0);

	return (ans >> 1) % i64(1e9);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14284 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 7 ms 14384 KB Output is correct
4 Correct 8 ms 14320 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct
6 Correct 8 ms 14384 KB Output is correct
7 Correct 8 ms 14368 KB Output is correct
8 Correct 9 ms 14384 KB Output is correct
9 Correct 8 ms 14412 KB Output is correct
10 Correct 8 ms 14388 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14764 KB Output is correct
2 Correct 13 ms 14888 KB Output is correct
3 Correct 11 ms 15068 KB Output is correct
4 Correct 12 ms 15012 KB Output is correct
5 Correct 13 ms 15236 KB Output is correct
6 Correct 12 ms 15260 KB Output is correct
7 Correct 17 ms 15252 KB Output is correct
8 Correct 12 ms 15288 KB Output is correct
9 Correct 13 ms 15292 KB Output is correct
10 Correct 13 ms 15308 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 24220 KB Output is correct
2 Correct 69 ms 23960 KB Output is correct
3 Correct 208 ms 38996 KB Output is correct
4 Correct 189 ms 38144 KB Output is correct
5 Correct 512 ms 62864 KB Output is correct
6 Correct 482 ms 62124 KB Output is correct
7 Correct 431 ms 61636 KB Output is correct
8 Correct 507 ms 62708 KB Output is correct
9 Correct 468 ms 62040 KB Output is correct
10 Correct 508 ms 60120 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 23136 KB Output is correct
2 Correct 75 ms 23888 KB Output is correct
3 Correct 281 ms 36156 KB Output is correct
4 Correct 230 ms 37444 KB Output is correct
5 Correct 618 ms 57704 KB Output is correct
6 Correct 522 ms 60928 KB Output is correct
7 Correct 661 ms 57812 KB Output is correct
8 Correct 560 ms 60328 KB Output is correct
9 Correct 502 ms 59208 KB Output is correct
10 Correct 547 ms 60204 KB Output is correct