Submission #547253

#	Time	Username	Problem	Language	Result	Execution time	Memory
547253		MilosMilutinovic	Ideal city (IOI12_city)	C++14	100 / 100	874 ms	30372 KiB

city

#include <bits/stdc++.h>

using namespace std;

const int N = 100000, MD = 1000000000;

int eo[N], *ej[N], vis[N], sz[N], cc[N], vis_[N];
map<pair<int, int>, int> aa, bb;
long long dp[N], ans;

int add(int x, int y) { return x + y > MD ? x + y - MD : x + y; }

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], 2 * o * sizeof *ej[i]);
	ej[i][o] = j;
}

void dfs1(int i, int d, int st) {
	int o;

	dp[st] += d * cc[i], sz[i] = cc[i], vis[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (!vis[j]) {
			dfs1(j, d + 1, st);
			sz[i] += sz[j];
		}
	}
}

void dfs2(int i, int p, int st) {
	int o;

	ans += dp[i] * cc[i], vis_[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (vis_[j] == 1)
			continue;
		dp[j] = dp[i];
		dp[j] -= sz[j];
		dp[j] += sz[st] - sz[j];
		dfs2(j, i, st);
	}
}

int solve(int n, int *x, int *y) {
	int i, _, x_;

	aa.clear(), bb.clear();
	for (i = 0; i < n; i++)
		bb[{x[i], y[i]}] = 1;
	for (i = 0, _ = 0; i < n; i++) {
		if (aa[{x[i], y[i]}] != 0)
			continue;
		aa[{x[i], y[i]}] = ++_;
		x_ = x[i];
		while (bb[{--x_, y[i]}] == 1)
			aa[{x_, y[i]}] = _;
		x_ = x[i];
		while (bb[{++x_, y[i]}] == 1)
			aa[{x_, y[i]}] = _;
	}
	memset(cc, 0, (_ + 1) * sizeof *cc);
	for (i = 0; i < n; i++)
		cc[aa[{x[i], y[i]}]]++;
	for (i = 0; i < n; i++)
		eo[i] = 0, ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n; i++)
		if (aa[{x[i], y[i] + 1}] != 0)
			append(aa[{x[i], y[i]}], aa[{x[i], y[i] + 1}]), append(aa[{x[i], y[i] + 1}], aa[{x[i], y[i]}]);
	ans = 0;
	for (i = 1; i <= _; i++)
		if (!vis[i]) {
			dp[i] = 0;
			dfs1(i, 0, i);
			dfs2(i, i, i);
		}
	for (i = 1; i <= _; i++)
		vis[i] = vis_[i] = 0;
	return (ans / 2) % MD;
}

int DistanceSum(int n, int *x, int *y) {
	return add(solve(n, x, y), solve(n, y, x));
}

Compilation message (stderr)

city.cpp: In function 'void append(int, int)':
city.cpp:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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