oj.uz

Submission #17235

# Submission time Handle Problem Language Result Execution time Memory
17235 2015-11-09T12:56:50 Z erdemkiraz Ideal city (IOI12_city) C++
100 / 100
 214 ms 20232 KB 
#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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6284 KB Output is correct
2 Correct 0 ms 6152 KB Output is correct
3 Correct 2 ms 6288 KB Output is correct
4 Correct 2 ms 6288 KB Output is correct
5 Correct 4 ms 6420 KB Output is correct
6 Correct 2 ms 6288 KB Output is correct
7 Correct 2 ms 6420 KB Output is correct
8 Correct 4 ms 6288 KB Output is correct
9 Correct 4 ms 6288 KB Output is correct
10 Correct 0 ms 6288 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7548 KB Output is correct
2 Correct 21 ms 7548 KB Output is correct
3 Correct 61 ms 9712 KB Output is correct
4 Correct 58 ms 9844 KB Output is correct
5 Correct 129 ms 13272 KB Output is correct
6 Correct 122 ms 13404 KB Output is correct
7 Correct 136 ms 13536 KB Output is correct
8 Correct 132 ms 13140 KB Output is correct
9 Correct 122 ms 13744 KB Output is correct
10 Correct 164 ms 19864 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8868 KB Output is correct
2 Correct 32 ms 8340 KB Output is correct
3 Correct 95 ms 13144 KB Output is correct
4 Correct 85 ms 11700 KB Output is correct
5 Correct 214 ms 20004 KB Output is correct
6 Correct 171 ms 15888 KB Output is correct
7 Correct 212 ms 20232 KB Output is correct
8 Correct 175 ms 16084 KB Output is correct
9 Correct 159 ms 15384 KB Output is correct
10 Correct 154 ms 15120 KB Output is correct