oj.uz

Submission #105138

# Submission time Handle Problem Language Result Execution time Memory
105138 2019-04-10T16:51:23 Z eriksuenderhauf Ideal city (IOI12_city) C++11
100 / 100
 144 ms 41236 KB 
//#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33408 KB Output is correct
2 Correct 30 ms 33272 KB Output is correct
3 Correct 33 ms 33144 KB Output is correct
4 Correct 33 ms 33220 KB Output is correct
5 Correct 32 ms 33284 KB Output is correct
6 Correct 30 ms 33152 KB Output is correct
7 Correct 31 ms 33152 KB Output is correct
8 Correct 30 ms 33400 KB Output is correct
9 Correct 31 ms 33280 KB Output is correct
10 Correct 31 ms 33272 KB Output is correct
11 Correct 32 ms 33144 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33252 KB Output is correct
2 Correct 34 ms 33272 KB Output is correct
3 Correct 35 ms 33344 KB Output is correct
4 Correct 35 ms 33340 KB Output is correct
5 Correct 33 ms 33344 KB Output is correct
6 Correct 34 ms 33408 KB Output is correct
7 Correct 38 ms 33280 KB Output is correct
8 Correct 34 ms 33276 KB Output is correct
9 Correct 33 ms 33296 KB Output is correct
10 Correct 38 ms 33272 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 34168 KB Output is correct
2 Correct 49 ms 34296 KB Output is correct
3 Correct 78 ms 35708 KB Output is correct
4 Correct 71 ms 35620 KB Output is correct
5 Correct 122 ms 38612 KB Output is correct
6 Correct 104 ms 38264 KB Output is correct
7 Correct 109 ms 38396 KB Output is correct
8 Correct 109 ms 38808 KB Output is correct
9 Correct 110 ms 37836 KB Output is correct
10 Correct 127 ms 41236 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 34352 KB Output is correct
2 Correct 62 ms 34552 KB Output is correct
3 Correct 89 ms 36216 KB Output is correct
4 Correct 93 ms 36088 KB Output is correct
5 Correct 122 ms 39260 KB Output is correct
6 Correct 126 ms 38776 KB Output is correct
7 Correct 144 ms 39288 KB Output is correct
8 Correct 122 ms 38732 KB Output is correct
9 Correct 125 ms 38492 KB Output is correct
10 Correct 137 ms 38392 KB Output is correct