Submission #105138

#	Time	Username	Problem	Language	Result	Execution time	Memory
105138		eriksuenderhauf	Ideal city (IOI12_city)	C++11	100 / 100	144 ms	41236 KiB

city

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int INF = 2147483647;
const int MAXN = 3e5 + 5;
vi x[MAXN], y[MAXN], adjV[MAXN], adjH[MAXN];
int vV[MAXN], vH[MAXN];
ll dp1[MAXN], dp2[MAXN];
int n, cntV = 0, cntH = 0;

void dfsH1(int u, int p) {
	dp1[u] = vH[u];
	for (int v: adjH[u]) {
		if (v != p) {
			dfsH1(v, u);
			dp1[u] += dp1[v];
		}
	}
}

void dfsH2(int u, int p) {
	if (p != -1)
		dp2[u] = dp2[p] + dp1[p] - dp1[u];
	else
		dp2[u] = 0;
	for (int v: adjH[u])
		if (v != p)
			dfsH2(v, u);
}

void dfsV1(int u, int p) {
	dp1[u] = vV[u];
	for (int v: adjV[u]) {
		if (v != p) {
			dfsV1(v, u);
			dp1[u] += dp1[v];
		}
	}
}

void dfsV2(int u, int p) {
	if (p != -1)
		dp2[u] = dp2[p] + dp1[p] - dp1[u];
	else
		dp2[u] = 0;
	for (int v: adjV[u])
		if (v != p)
			dfsV2(v, u);
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	int miX = INF, miY = INF;
	for (int i = 0; i < N; i++) {
		miX = min(miX, X[i]);
		miY = min(miY, Y[i]);
	}
	for (int i = 0; i < N; i++) {
		x[X[i] - miX].pb(Y[i] - miY);
		y[Y[i] - miY].pb(X[i] - miX);
	}
	map<int,int> prevX, curX, prevY, curY;
	for (int i = 0; i < N; i++) {
		sort(x[i].begin(), x[i].end()); // vert
		for (int j = 0; j < x[i].size(); j++) {
			int k = j;
			while (k < x[i].size() && x[i][j] - j == x[i][k] - k) {
				curX[x[i][k]] = cntV;
				if (prevX.find(x[i][k]) != prevX.end()) {
					int u = prevX[x[i][k]];
					adjV[cntV].pb(u);
					adjV[u].pb(cntV);
				}
				k++;
			}
			vV[cntV++] = k - j;
			j = k - 1;
		}
		swap(prevX, curX);
		curX.clear();
		sort(y[i].begin(), y[i].end()); // hori
		for (int j = 0; j < y[i].size(); j++) {
			int k = j;
			while (k < y[i].size() && y[i][j] - j == y[i][k] - k) {
				curY[y[i][k]] = cntH;
				if (prevY.find(y[i][k]) != prevY.end()) {
					int u = prevY[y[i][k]];
					adjH[cntH].pb(u);
					adjH[u].pb(cntH);
				}
				k++;
			}
			vH[cntH++] = k - j;
			j = k - 1;
		}
		swap(prevY, curY);
		curY.clear();
	}
	for (int i = 0; i < cntH; i++) {
		//sort(adjH[i].begin(), adjH[i].end());
		adjH[i].erase(unique(adjH[i].begin(), adjH[i].end()), adjH[i].end());
	}
	for (int i = 0; i < cntV; i++) {
		//sort(adjV[i].begin(), adjV[i].end());
		adjV[i].erase(unique(adjV[i].begin(), adjV[i].end()), adjV[i].end());
	}
	ll ret = 0;
	dfsH1(0, -1);
	dfsH2(0, -1);
	for (int i = 0; i < cntH; i++) {
		//cout << vH[i] << "\n";
		ret += 1ll * (ll) dp1[i] * 1ll * (ll) dp2[i];
	}
	//cout << "\n";
	memset(dp1, 0, sizeof dp1);
	memset(dp2, 0, sizeof dp2);
	dfsV1(0, -1);
	dfsV2(0, -1);
	for (int i = 0; i < cntV; i++) {
		//cout << vV[i] << "\n";
		ret += 1ll * (ll) dp1[i] * 1ll * (ll) dp2[i];
	}
	return ret % 1000000000;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < x[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
city.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (k < x[i].size() && x[i][j] - j == x[i][k] - k) {
           ~~^~~~~~~~~~~~~
city.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < y[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
city.cpp:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (k < y[i].size() && y[i][j] - j == y[i][k] - k) {
           ~~^~~~~~~~~~~~~

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