oj.uz

Submission #761802

# Submission time Handle Problem Language Result Execution time Memory
761802 2023-06-20T09:47:34 Z SanguineChameleon Ideal city (IOI12_city) C++17
100 / 100
 262 ms 16316 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
const long long mod = 1e9;
vector<int> adj[maxN];
pair<int, int> ranges[maxN];
int sum[maxN];
pair<int, int> pos[maxN];
map<pair<int, int>, int> comp_id;
set<pair<int, int>> edges;
int comp_cnt;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second < p2.second;
}

int get_id(int x, int y) {
	auto it = comp_id.find(make_pair(x, y));
	if (it == comp_id.end()) {
		return -1;
	}
	else {
		return it->second;
	}
}

long long res = 0;

void dfs(int u, int p) {
	for (auto v: adj[u]) {
		if (v != p) {
			dfs(v, u);
			sum[u] += sum[v];
		}
	}
}

int DistanceSum(int N, int *X, int *Y) {
	for (int i = 1; i <= N; i++) {
		pos[i].first = X[i - 1];
		pos[i].second = Y[i - 1];
	}
	res = 0;
	for (int iter = 0; iter < 2; iter++) {
		comp_id.clear();
		edges.clear();
		for (int i = 1; i <= N; i++) {
			comp_id[make_pair(pos[i].first, pos[i].second)] = -2;
			adj[i].clear();
		}
		sort(pos + 1, pos + N + 1, cmp);
		comp_cnt = 0;
		for (int i = 1; i <= N; i++) {
			int x = pos[i].first;
			int y = pos[i].second;
			int id = get_id(x, y - 1);
			if (id == -1) {
				id = ++comp_cnt;
				ranges[id].first = y;
			}
			comp_id[make_pair(x, y)] = id;
			if (get_id(x, y + 1) == -1) {
				ranges[id].second = y;
				sum[id] = ranges[id].second - ranges[id].first + 1;
			}
		}
		for (int i = 1; i <= N; i++) {
			int x = pos[i].first;
			int y = pos[i].second;
			int u = get_id(x, y);
			int v = get_id(x - 1, y);
			if (u != -1 && v != -1) {
				edges.emplace(u, v);
				edges.emplace(v, u);
			}
		}
		for (auto e: edges) {
			adj[e.first].push_back(e.second);
		}
		dfs(1, -1);
		for (int i = 1; i <= comp_cnt; i++) {
			res += 1LL * sum[i] * (sum[1] - sum[i]);
		}
		for (int i = 1; i <= N; i++) {
			swap(pos[i].first, pos[i].second);
		}
	}
	res %= mod;
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2848 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4332 KB Output is correct
2 Correct 38 ms 4420 KB Output is correct
3 Correct 102 ms 6676 KB Output is correct
4 Correct 108 ms 6788 KB Output is correct
5 Correct 223 ms 10552 KB Output is correct
6 Correct 242 ms 10812 KB Output is correct
7 Correct 201 ms 10904 KB Output is correct
8 Correct 243 ms 10548 KB Output is correct
9 Correct 249 ms 11112 KB Output is correct
10 Correct 228 ms 16220 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5344 KB Output is correct
2 Correct 38 ms 5028 KB Output is correct
3 Correct 118 ms 9392 KB Output is correct
4 Correct 106 ms 8396 KB Output is correct
5 Correct 253 ms 16044 KB Output is correct
6 Correct 230 ms 12784 KB Output is correct
7 Correct 254 ms 16316 KB Output is correct
8 Correct 262 ms 12948 KB Output is correct
9 Correct 261 ms 12268 KB Output is correct
10 Correct 247 ms 11980 KB Output is correct