Submission #158860

#	Time	Username	Problem	Language	Result	Execution time	Memory
158860		maruii	Ideal city (IOI12_city)	C++14	100 / 100	63 ms	11896 KiB

city

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int mod = 1e9;

int N;
pii P[100005];
vector<pii> vec[100005];
vector<int> edge[100005];
int sz[100005];

int dfs(int x, int p) {
	int ret = 0;
	for (auto i : edge[x]) {
		if (i == p) continue;
		ret += dfs(i, x);
		ret %= mod;
		sz[x] += sz[i];
	}
	return (ret + 1ll * (N - sz[x]) * sz[x] % mod) % mod;
}

int solve() {
	sort(P, P + N);
	int x0 = P[0].ff;
	for (int i = 0, j = 0; i < N; i = ++j) {
		while (j + 1 < N && P[j + 1].ff == P[i].ff && P[j + 1].ss == P[j].ss + 1) j++;
		vec[P[i].ff - x0].emplace_back(P[i].ss, P[j].ss);
	}
	for (int i = 0; i <= P[N - 1].ff - x0; ++i) sort(vec[i].begin(), vec[i].end());
	int cnt = 0;
	for (int i = 0; i < P[N - 1].ff - x0; ++i) {
		for (int j = 0, k = 0; j < vec[i].size(); ++j) {
			sz[cnt + j] = vec[i][j].ss - vec[i][j].ff + 1;
			while (k + 1 < vec[i + 1].size() && vec[i + 1][k + 1].ff <= vec[i][j].ss) {
				if (vec[i][j].ff <= vec[i + 1][k].ss) {
					edge[cnt + j].push_back(cnt + vec[i].size() + k);
					edge[cnt + vec[i].size() + k].push_back(cnt + j);
				}
				k++;
			}

			if (vec[i + 1][k].ff <= vec[i][j].ss && vec[i][j].ff <= vec[i + 1][k].ss) {
				edge[cnt + j].push_back(cnt + vec[i].size() + k);
				edge[cnt + vec[i].size() + k].push_back(cnt + j);
			}
		}
		cnt += vec[i].size();
	}
	for (auto i : vec[P[N - 1].ff - x0]) sz[cnt++] = i.ss - i.ff + 1;
	for (int i = 0; i <= P[N - 1].ff - x0; ++i) vec[i].clear();
	int t = dfs(0, 0);
	for (int i = 0; i < cnt; ++i) edge[i].clear();
	return t;
}

int DistanceSum(int NN, int *X, int *Y) {
	N = NN;
	for (int i = 0; i < N; ++i) P[i] = {X[i], Y[i]};
	int ans = solve();
	for (int i = 0; i < N; ++i) swap(P[i].ff, P[i].ss);
	return ans = (ans + solve()) % mod;
}

Compilation message (stderr)

city.cpp: In function 'int solve()':
city.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0, k = 0; j < vec[i].size(); ++j) {
                          ~~^~~~~~~~~~~~~~~
city.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (k + 1 < vec[i + 1].size() && vec[i + 1][k + 1].ff <= vec[i][j].ss) {
           ~~~~~~^~~~~~~~~~~~~~~~~~~

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