Submission #17235

#	Time	Username	Problem	Language	Result	Execution time	Memory
17235		erdemkiraz	Ideal city (IOI12_city)	C++98	100 / 100	214 ms	20232 KiB

city

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;
const int mod = 1e9;

inline int add(int x, int y) {
	return x + y >= mod ? x + y - mod : x + y;
}

inline int mul(int x, int y) {
	return (ll) x * y % mod;
}

int n, ans;
ii a[N];
int gr[N], sz[N];
vector < int > v[N];
map < ii, int > M, p;

void add(int i) {
	int x = a[i].first;
	int y = a[i].second;
	if(p.find(ii(x - 1, y)) != p.end()) {
		int j = p[ii(x - 1, y)];
		if(!M[ii(gr[i], gr[j])]) {
			M[ii(gr[i], gr[j])] = M[ii(gr[j], gr[i])] = 1;
			//printf("i, j = %d %d\n", gr[i], gr[j]);
			v[gr[i]].push_back(gr[j]);
			v[gr[j]].push_back(gr[i]);
		}
	}
	//cout << flush;
}

int ch[N];

void dfs(int p, int x) {
	ch[x] = sz[x];
	foreach(it, v[x]) {
		int u = *it;
		if(u != p) {
			dfs(x, u);
			ch[x] += ch[u];
			ans = add(ans, mul(ch[u], n - ch[u]));
		}
	}
}

void solve() {
	M.clear();
	p.clear();
	for(int i = 0; i < n; i++)
		v[i].clear();
	sort(a, a + n);
	for(int i = 0; i < n; i++) {
		int j = i;
		gr[i] = i;
		sz[i] = 1;
		p[a[i]] = i;
		add(i);
		while(j + 1 < n and a[j + 1] == ii(a[j].first, a[j].second + 1)) {
			j++;
			gr[j] = i;
			sz[i]++;
			p[a[j]]= j;
			add(j);
		}
		i = j;
	}
	dfs(-1, 0);
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	for(int i = 0; i < n; i++) {
		a[i] = ii(X[i], Y[i]);
	}
	solve();
	for(int i = 0; i < n; i++) {
		a[i] = ii(Y[i], X[i]);
	}
	solve();
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45