Submission #58414

#	Time	Username	Problem	Language	Result	Execution time	Memory
58414		kingpig9	Ideal city (IOI12_city)	C++11	100 / 100	509 ms	28312 KiB

city

#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 (stderr)

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