oj.uz

Submission #158860

# Submission time Handle Problem Language Result Execution time Memory
158860 2019-10-19T07:42:28 Z maruii Ideal city (IOI12_city) C++14
100 / 100
 63 ms 11896 KB 
#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

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.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5624 KB Output is correct
2 Correct 14 ms 5624 KB Output is correct
3 Correct 26 ms 6392 KB Output is correct
4 Correct 26 ms 6428 KB Output is correct
5 Correct 47 ms 7600 KB Output is correct
6 Correct 49 ms 7644 KB Output is correct
7 Correct 48 ms 7800 KB Output is correct
8 Correct 48 ms 7408 KB Output is correct
9 Correct 49 ms 7892 KB Output is correct
10 Correct 54 ms 11896 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6008 KB Output is correct
2 Correct 16 ms 5880 KB Output is correct
3 Correct 34 ms 7672 KB Output is correct
4 Correct 31 ms 7032 KB Output is correct
5 Correct 63 ms 9596 KB Output is correct
6 Correct 53 ms 8440 KB Output is correct
7 Correct 63 ms 9720 KB Output is correct
8 Correct 54 ms 8576 KB Output is correct
9 Correct 51 ms 8168 KB Output is correct
10 Correct 51 ms 8036 KB Output is correct