oj.uz

Submission #58414

# Submission time Handle Problem Language Result Execution time Memory
58414 2018-07-17T18:40:24 Z kingpig9 Ideal city (IOI12_city) C++11
100 / 100
 509 ms 28312 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MOD = 2e9;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int add (int x, int y) {
	int r = (ll(x) + y) % MOD;
	if (r < 0) {
		r += MOD;
	}
	return r;
}

void addeq (int &x, int y) {
	x = add(x, y);
}

int mult (int x, int y) {
	return ll(x) * y % MOD;
}

int N, V;
int X[MAXN], Y[MAXN];
int bel[MAXN];
map<pii, int> mp;
set<pii> edges;
int W[MAXN];	//weight of it
vector<int> ys[MAXN];
vector<int> adj[MAXN];

//let's go now
int sub[MAXN];
int sumd[MAXN];

void dfs1 (int x, int p, int d) {
	addeq(sumd[0], mult(d, W[x]));
	sub[x] = W[x];
	for (int y : adj[x]) {
		if (y != p) {
			dfs1(y, x, d + 1);
			sub[x] += sub[y];
		}
	}
}

void dfs2 (int x, int p) {
	for (int y : adj[x]) {
		if (y != p) {
			sumd[y] = add(sumd[x], N - 2 * sub[y]);
			dfs2(y, x);
		}
	}
}

int go() {
#warning reset
	mp.clear();
	edges.clear();
	for (int i = 0; i < MAXN; i++) {
		ys[i].clear();
		adj[i].clear();
		W[i] = 0;
		sub[i] = 0;
		sumd[i] = 0;
	}
	V = 0;

	for (int i = 0; i < N; i++) {
		ys[X[i]].push_back(Y[i]);
		mp[{X[i], Y[i]}] = i;
	}

	for (int i = 0; i < MAXN; i++) {
		sort(all(ys[i]));
		//components
		for (int j = 0; j < ys[i].size(); ) {
			int k = j;
			int comp = V++;
			for (; k < ys[i].size() && ys[i][k] - ys[i][j] == k - j; k++) {
				W[comp]++;
				bel[mp.at({i, ys[i][k]})] = comp;

				if (i) {
					//connect with previous row
					auto it = mp.find({i - 1, ys[i][k]});
					if (it != mp.end()) {
						edges.emplace(bel[it->se], comp);
					}
				}
			}
			j = k;
		}
	}

	//make actual graph
	for (pii p : edges) {
		adj[p.fi].push_back(p.se);
		adj[p.se].push_back(p.fi);
	}

	dfs1(0, -1, 0);
	dfs2(0, -1);

	int ans = 0;
	for (int i = 0; i < V; i++) {
		addeq(ans, mult(W[i], sumd[i]));
	}
	return ans;
}

int DistanceSum (int nn, int *xx, int *yy) {
	N = nn;
	int xmin = *min_element(xx, xx + N), ymin = *min_element(yy, yy + N);
	for (int i = 0; i < N; i++) {
		X[i] = xx[i] - xmin;
		Y[i] = yy[i] - ymin;
	}

	//find w(y) * d(x, y)
	int ansx = go();
	for (int i = 0; i < N; i++) {
		swap(X[i], Y[i]);
	}
	int ansy = go();
	return add(ansx, ansy) / 2;
}

Compilation message

city.cpp:66:2: warning: #warning reset [-Wcpp]
 #warning reset
  ^~~~~~~
city.cpp: In function 'int go()':
city.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < ys[i].size(); ) {
                   ~~^~~~~~~~~~~~~~
city.cpp:89:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (; k < ys[i].size() && ys[i][k] - ys[i][j] == k - j; k++) {
           ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6264 KB Output is correct
2 Correct 12 ms 6472 KB Output is correct
3 Correct 11 ms 6472 KB Output is correct
4 Correct 13 ms 6684 KB Output is correct
5 Correct 12 ms 6684 KB Output is correct
6 Correct 11 ms 6684 KB Output is correct
7 Correct 13 ms 6684 KB Output is correct
8 Correct 11 ms 6684 KB Output is correct
9 Correct 12 ms 6684 KB Output is correct
10 Correct 12 ms 6692 KB Output is correct
11 Correct 11 ms 6708 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6872 KB Output is correct
2 Correct 14 ms 6880 KB Output is correct
3 Correct 14 ms 6904 KB Output is correct
4 Correct 13 ms 6932 KB Output is correct
5 Correct 16 ms 7088 KB Output is correct
6 Correct 14 ms 7088 KB Output is correct
7 Correct 14 ms 7132 KB Output is correct
8 Correct 17 ms 7132 KB Output is correct
9 Correct 15 ms 7132 KB Output is correct
10 Correct 14 ms 7132 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8976 KB Output is correct
2 Correct 64 ms 9252 KB Output is correct
3 Correct 155 ms 12124 KB Output is correct
4 Correct 150 ms 12840 KB Output is correct
5 Correct 372 ms 17920 KB Output is correct
6 Correct 372 ms 19228 KB Output is correct
7 Correct 400 ms 19892 KB Output is correct
8 Correct 381 ms 19972 KB Output is correct
9 Correct 459 ms 21376 KB Output is correct
10 Correct 475 ms 26624 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 26624 KB Output is correct
2 Correct 60 ms 26624 KB Output is correct
3 Correct 194 ms 26624 KB Output is correct
4 Correct 170 ms 26624 KB Output is correct
5 Correct 481 ms 26744 KB Output is correct
6 Correct 448 ms 26744 KB Output is correct
7 Correct 509 ms 28312 KB Output is correct
8 Correct 393 ms 28312 KB Output is correct
9 Correct 392 ms 28312 KB Output is correct
10 Correct 411 ms 28312 KB Output is correct