oj.uz

Submission #61757

# Submission time Handle Problem Language Result Execution time Memory
61757 2018-07-26T14:44:53 Z aome Ideal city (IOI12_city) C++17
100 / 100
 763 ms 34488 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int mod = 1e9;
const int INF = 2147483646;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n;
int res;
int sz[N];
int cnt[N];
int par[N];
int sum2[N];
int X[N], Y[N];
bool visit[N];
vector<int> G[N];
vector<int> G2[N];
vector<int> vec[N];
pair<int, int> L[N], R[N];
map< pair<int, int>, int > label;

int find(int u) {
	return u == par[u] ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	par[find(u)] = find(v);
}

struct Data {
	int val, cnt, type;

	bool operator < (const Data& rhs) const {
		return val < rhs.val;
	}
};

int calc(vector<Data> &vec) {
	sort(vec.begin(), vec.end());
	int ret = 0, sum;
	sum = 0;
	for (auto i : vec) sum2[i.type] = 0;
	for (auto i : vec) {
		int tmp = (sum + mod - sum2[i.type]) % mod;
		ret = (ret + 1LL * tmp * i.val % mod * i.cnt) % mod;
		sum = (sum + i.cnt) % mod;
		sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
	}
	reverse(vec.begin(), vec.end());
	sum = 0;
	for (auto i : vec) sum2[i.type] = 0;
	for (auto i : vec) {
		int tmp = (sum + mod - sum2[i.type]) % mod;
		ret = (ret + mod - 1LL * tmp * i.val % mod * i.cnt % mod) % mod;
		sum = (sum + i.cnt) % mod;
		sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
	}
	return ret;
}

void dfs(int u) {
	sz[u] = vec[u].size();
	visit[u] = 1;
	vector<Data> vec2;
	for (auto i : vec[u]) {
		for (auto j : G[i]) {
			int v = find(j);
			if (visit[v]) continue;
			// cout << u << ' ' << v << '\n';
			L[v] = {INF, 0}, R[v] = {-INF, 0};
			for (auto k : vec[v]) {
				for (auto l : G[k]) {
					if (find(l) != u) continue;
					L[v] = min(L[v], {Y[k], k});
					R[v] = max(R[v], {Y[k], k});
				}
			}
			dfs(v), sz[u] += sz[v];
			for (auto k : vec[v]) {
				for (auto l : G[k]) {
					if (find(l) != u) continue;
					cnt[l] += cnt[k];
					vec2.push_back({Y[k], cnt[k], v});
					res = (res + 1LL * cnt[k] * (n - sz[v])) % mod;
					// cout << k << ' ' << cnt[k] << ' ' << n - sz[v] << '\n';
				}
			}
		}
	}
	for (auto i : vec[u]) {
		vec2.push_back({Y[i], 1, i});
	}
	int tmp = calc(vec2);
	res = (res + tmp) % mod;
	// cout << "#at " << u << '\n';
	// for (auto i : vec2) cout << i.first << ' ' << i.second << '\n';
	// cout << tmp << '\n';
	if (u == find(0)) return;
	for (auto i : vec[u]) {
		if (L[u].first <= Y[i] && Y[i] <= R[u].first) continue;
		if (Y[i] < L[u].first) {
			res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (L[u].first - Y[i])) % mod;
			cnt[L[u].second] += cnt[i];
		}
		if (Y[i] > R[u].first) {
			res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (Y[i] - R[u].first)) % mod;
			cnt[R[u].second] += cnt[i];
		}
	}
}

int DistanceSum(int _n, int *_X, int *_Y) {
	n = _n;
	for (int i = 0; i < n; ++i) X[i] = _X[i], Y[i] = _Y[i];
	for (int i = 0; i < n; ++i) {
		label[{X[i], Y[i]}] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			int x = X[i] + dx[j], y = Y[i] + dy[j];
			if (label.count({x, y})) {
				int id = label[{x, y}];
				G[i].push_back(id);
			}
		}
	}
	for (int i = 0; i < n; ++i) par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (X[i] == X[j]) join(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		cnt[i] = 1, vec[find(i)].push_back(i);
	}
	dfs(find(0));
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 11 ms 7532 KB Output is correct
3 Correct 9 ms 7532 KB Output is correct
4 Correct 10 ms 7532 KB Output is correct
5 Correct 10 ms 7532 KB Output is correct
6 Correct 10 ms 7532 KB Output is correct
7 Correct 10 ms 7608 KB Output is correct
8 Correct 12 ms 7664 KB Output is correct
9 Correct 11 ms 7664 KB Output is correct
10 Correct 10 ms 7664 KB Output is correct
11 Correct 10 ms 7664 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7732 KB Output is correct
2 Correct 12 ms 7748 KB Output is correct
3 Correct 12 ms 7884 KB Output is correct
4 Correct 11 ms 7956 KB Output is correct
5 Correct 16 ms 8144 KB Output is correct
6 Correct 16 ms 8172 KB Output is correct
7 Correct 13 ms 8188 KB Output is correct
8 Correct 15 ms 8220 KB Output is correct
9 Correct 16 ms 8220 KB Output is correct
10 Correct 15 ms 8248 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 11140 KB Output is correct
2 Correct 84 ms 11420 KB Output is correct
3 Correct 309 ms 15812 KB Output is correct
4 Correct 276 ms 16492 KB Output is correct
5 Correct 670 ms 24528 KB Output is correct
6 Correct 649 ms 25252 KB Output is correct
7 Correct 763 ms 26324 KB Output is correct
8 Correct 686 ms 26324 KB Output is correct
9 Correct 657 ms 27896 KB Output is correct
10 Correct 662 ms 33736 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 33736 KB Output is correct
2 Correct 96 ms 33736 KB Output is correct
3 Correct 289 ms 33736 KB Output is correct
4 Correct 251 ms 33736 KB Output is correct
5 Correct 655 ms 33736 KB Output is correct
6 Correct 642 ms 33736 KB Output is correct
7 Correct 593 ms 33736 KB Output is correct
8 Correct 574 ms 33736 KB Output is correct
9 Correct 578 ms 33736 KB Output is correct
10 Correct 512 ms 34488 KB Output is correct