Submission #779684

#	Time	Username	Problem	Language	Result	Execution time	Memory
779684		Sohsoh84	Ideal city (IOI12_city)	C++17	100 / 100	103 ms	10356 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45