oj.uz

Submission #803213

# Submission time Handle Problem Language Result Execution time Memory
803213 2023-08-03T01:12:58 Z pavement Ideal city (IOI12_city) C++17
100 / 100
 150 ms 19080 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

using ll = long long;
using ii = pair<int, int>;

const int MOD = (int)1e9;
int rep[100005], dist[200005];
bool vis[200005];
ii row_to_1[100005], col_to_1[100005], row_to_2[100005], col_to_2[100005];
vector<int> adj[200005];
vector<ii> row[100005], col[100005];
queue<int> Q;

namespace ufds {
	int lnk[100005], sz[100005];
	
	void init(int n) {
		iota(lnk, lnk + n, 0);
		fill(sz, sz + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[b] > sz[a]) swap(a, b);
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

int DistanceSum(int N, int X[], int Y[]) {
	int ans = 0, min_X = *min_element(X, X + N), min_Y = *min_element(Y, Y + N);
	for (int i = 0; i < N; i++) {
		X[i] -= min_X;
		Y[i] -= min_Y;
		assert(0 <= X[i] && X[i] < N && 0 <= Y[i] && Y[i] < N);
		row[X[i]].eb(Y[i], i);
		col[Y[i]].eb(X[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(row[i].begin(), row[i].end());
		sort(col[i].begin(), col[i].end());
	}
	for (auto [dim, to] : {mp(row, row_to_1), mp(col, col_to_1)}) {
		ufds::init(N);
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			int prv_j = -1, prv_idx = -1;
			for (auto [j, cur] : dim[i]) {
				int upper = -1, idx;
				if (i) {
					auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0));
					if (it != dim[i - 1].end() && it->first == j) {
						upper = ufds::find(rep[it->second]);
					}
				}
				if (upper == -1) {
					idx = cnt++;
				} else {
					idx = upper;
					ufds::sz[upper]++;
				}
				rep[cur] = idx;
				if (prv_j != -1 && prv_j + 1 == j) {
					if (ufds::find(prv_idx) != ufds::find(idx)) {
						ufds::unite(prv_idx, idx);
					}
				}
				prv_j = j;
				prv_idx = idx;
			}
			for (auto [j, cur] : dim[i]) {
				to[cur] = mp(ufds::find(rep[cur]), ufds::sz[ufds::find(rep[cur])]);
			}
		}
	}
	for (auto [dim, to] : {mp(row, row_to_2), mp(col, col_to_2)}) {
		ufds::init(N);
		int cnt = 0;
		for (int i = N - 1; i >= 0; i--) {
			int prv_j = -1, prv_idx = -1;
			for (auto [j, cur] : dim[i]) {
				int upper = -1, idx;
				if (i + 1 < N) {
					auto it = lower_bound(dim[i + 1].begin(), dim[i + 1].end(), mp(j, 0));
					if (it != dim[i + 1].end() && it->first == j) {
						upper = ufds::find(rep[it->second]);
					}
				}
				if (upper == -1) {
					idx = cnt++;
				} else {
					idx = upper;
					ufds::sz[upper]++;
				}
				rep[cur] = idx;
				if (prv_j != -1 && prv_j + 1 == j) {
					if (ufds::find(prv_idx) != ufds::find(idx)) {
						ufds::unite(prv_idx, idx);
					}
				}
				prv_j = j;
				prv_idx = idx;
			}
			for (auto [j, cur] : dim[i]) {
				to[cur] = mp(ufds::find(rep[cur]), ufds::sz[ufds::find(rep[cur])]);
			}
		}
	}
	for (auto [dim, to_1, to_2] : {mt(row, row_to_1, row_to_2), mt(col, col_to_1, col_to_2)}) {
		for (int i = 1; i < N; i++) {
			vector<ii> nodes, edges;
			for (auto [j, cur] : dim[i]) {
				int upper = -1;
				if (i) {
					auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0));
					if (it != dim[i - 1].end() && it->first == j) {
						upper = it->second;
					}
				}
				if (upper != -1) {
					nodes.pb(mp(to_2[cur].first + N, to_2[cur].second));
					nodes.pb(mp(to_1[upper].first, to_1[upper].second));
					edges.eb(to_2[cur].first + N, to_1[upper].first);
				}
			}
			sort(nodes.begin(), nodes.end());
			nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
			for (auto [x, s] : nodes) {
				adj[x].clear();
			}
			for (auto [u, v] : edges) {
				adj[u].pb(v);
				adj[v].pb(u);
			}
			for (auto [x, s] : nodes) {
				for (auto [x2, _] : nodes) {
					vis[x2] = 0;
				}
				dist[x] = 0;
				vis[x] = 1;
				Q.push(x);
				while (!Q.empty()) {
					int a = Q.front();
					Q.pop();
					for (auto v : adj[a]) {
						if (!vis[v]) {
							vis[v] = 1;
							dist[v] = dist[a] + 1;
							Q.push(v);
						}
					}
				}
				for (auto [x2, s2] : nodes) {
					if (x < x2) ans = (ans + (ll)dist[x2] * s2 % MOD * (ll)s % MOD) % MOD;
				}
			}
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9892 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9856 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11348 KB Output is correct
2 Correct 14 ms 11380 KB Output is correct
3 Correct 26 ms 13556 KB Output is correct
4 Correct 35 ms 13452 KB Output is correct
5 Correct 49 ms 17740 KB Output is correct
6 Correct 54 ms 17408 KB Output is correct
7 Correct 48 ms 17216 KB Output is correct
8 Correct 48 ms 17732 KB Output is correct
9 Correct 55 ms 16988 KB Output is correct
10 Correct 62 ms 18252 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11396 KB Output is correct
2 Correct 20 ms 11580 KB Output is correct
3 Correct 77 ms 14472 KB Output is correct
4 Correct 49 ms 14188 KB Output is correct
5 Correct 149 ms 19080 KB Output is correct
6 Correct 85 ms 18380 KB Output is correct
7 Correct 150 ms 18892 KB Output is correct
8 Correct 88 ms 18444 KB Output is correct
9 Correct 98 ms 18352 KB Output is correct
10 Correct 79 ms 18256 KB Output is correct