oj.uz

Submission #105137

# Submission time Handle Problem Language Result Execution time Memory
105137 2019-04-10T16:50:31 Z eriksuenderhauf Ideal city (IOI12_city) C++11
32 / 100
 55 ms 34296 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);
}

ll 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;
}

Compilation message

city.cpp: In function 'll 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 37 ms 33144 KB Output is correct
2 Correct 33 ms 33144 KB Output is correct
3 Correct 31 ms 33144 KB Output is correct
4 Correct 35 ms 33148 KB Output is correct
5 Correct 34 ms 33176 KB Output is correct
6 Correct 34 ms 33280 KB Output is correct
7 Correct 32 ms 33280 KB Output is correct
8 Correct 30 ms 33272 KB Output is correct
9 Correct 33 ms 33280 KB Output is correct
10 Correct 31 ms 33272 KB Output is correct
11 Correct 33 ms 33152 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33280 KB Output is correct
2 Correct 33 ms 33272 KB Output is correct
3 Correct 36 ms 33280 KB Output is correct
4 Correct 34 ms 33356 KB Output is correct
5 Correct 36 ms 33400 KB Output is correct
6 Correct 36 ms 33272 KB Output is correct
7 Correct 38 ms 33400 KB Output is correct
8 Correct 34 ms 33272 KB Output is correct
9 Correct 33 ms 33272 KB Output is correct
10 Correct 39 ms 33272 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 34168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 34296 KB Output isn't correct
2 Halted 0 ms 0 KB -