oj.uz

Submission #779674

# Submission time Handle Problem Language Result Execution time Memory
779674 2023-07-11T16:04:21 Z Sohsoh84 Ideal city (IOI12_city) C++17
0 / 100
 19 ms 4732 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4732 KB Output isn't correct
2 Halted 0 ms 0 KB -