oj.uz

Submission #779684

# Submission time Handle Problem Language Result Execution time Memory
779684 2023-07-11T16:14:03 Z Sohsoh84 Ideal city (IOI12_city) C++17
100 / 100
 103 ms 10356 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define all(x)		(x).begin(),(x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e5 + 10;
const ll MOD = 1000000000;

int n, f[MAXN], sz;
vector<pll> vec;
ll ans = 0, dp[MAXN];
vector<int> adj[MAXN];

inline int get(ll x, ll y) {
	pll e = pll(x, y);
	auto it = lower_bound(all(vec), e);
	if (it != vec.end() && *it == e) return it - vec.begin() + 1;
	return 0;
}

void dfs(int v, int p) {
	for (int u : adj[v]) {
		if (u == p) continue;
		dfs(u, v);
		ans = (ans + 1ll * dp[u] * (n - dp[u])) % MOD;
		dp[v] += dp[u];
	}
}

inline void solve() {
	sz = 0;
	sort(all(vec));
	memset(f, 0, sizeof f);
	memset(dp, 0, sizeof dp);
	for (int i = 0; i < MAXN; i++)
		adj[i].clear();

	for (int i = 0; i < n; i++) {
		auto [x, y] = vec[i];
		if (get(x, y - 1)) f[i + 1] = f[get(x, y - 1)];
		else f[i + 1] = ++sz;

		dp[f[i + 1]]++;
		if (get(x - 1, y) && !(get(x, y - 1) && get(x - 1, y - 1))) 
			adj[f[get(x - 1, y)]].push_back(f[i + 1]), adj[f[i + 1]].push_back(f[get(x - 1, y)]);
	}

	dfs(1, 0);
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;	
	for (int i = 0; i < n; i++)
		vec.push_back({X[i], Y[i]});

	sort(all(vec));
	solve();

	for (auto& e : vec)
		swap(e.X, e.Y);
	solve();
	return ans % MOD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3864 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 4 ms 3924 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 3 ms 3924 KB Output is correct
8 Correct 4 ms 3924 KB Output is correct
9 Correct 3 ms 3840 KB Output is correct
10 Correct 3 ms 3924 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4400 KB Output is correct
2 Correct 19 ms 4572 KB Output is correct
3 Correct 49 ms 5580 KB Output is correct
4 Correct 44 ms 5576 KB Output is correct
5 Correct 96 ms 7144 KB Output is correct
6 Correct 95 ms 7116 KB Output is correct
7 Correct 90 ms 7376 KB Output is correct
8 Correct 90 ms 7092 KB Output is correct
9 Correct 90 ms 7276 KB Output is correct
10 Correct 89 ms 10356 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4556 KB Output is correct
2 Correct 19 ms 4728 KB Output is correct
3 Correct 49 ms 6100 KB Output is correct
4 Correct 46 ms 5956 KB Output is correct
5 Correct 92 ms 8388 KB Output is correct
6 Correct 90 ms 7752 KB Output is correct
7 Correct 103 ms 8552 KB Output is correct
8 Correct 92 ms 7700 KB Output is correct
9 Correct 94 ms 7340 KB Output is correct
10 Correct 96 ms 7280 KB Output is correct