Submission #761802

#	Time	Username	Problem	Language	Result	Execution time	Memory
761802		SanguineChameleon	Ideal city (IOI12_city)	C++17	100 / 100	262 ms	16316 KiB

city

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