oj.uz

Submission #547253

# Submission time Handle Problem Language Result Execution time Memory
547253 2022-04-10T05:29:57 Z MilosMilutinovic Ideal city (IOI12_city) C++14
100 / 100
 874 ms 30372 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 3 ms 580 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 6 ms 712 KB Output is correct
5 Correct 6 ms 908 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 6 ms 848 KB Output is correct
8 Correct 6 ms 844 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 6 ms 852 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5268 KB Output is correct
2 Correct 76 ms 5196 KB Output is correct
3 Correct 220 ms 12460 KB Output is correct
4 Correct 214 ms 12240 KB Output is correct
5 Correct 583 ms 24652 KB Output is correct
6 Correct 589 ms 24596 KB Output is correct
7 Correct 626 ms 24708 KB Output is correct
8 Correct 547 ms 24736 KB Output is correct
9 Correct 588 ms 24132 KB Output is correct
10 Correct 680 ms 27732 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6296 KB Output is correct
2 Correct 76 ms 5968 KB Output is correct
3 Correct 325 ms 15144 KB Output is correct
4 Correct 267 ms 14088 KB Output is correct
5 Correct 868 ms 29972 KB Output is correct
6 Correct 757 ms 26688 KB Output is correct
7 Correct 874 ms 30372 KB Output is correct
8 Correct 756 ms 26768 KB Output is correct
9 Correct 722 ms 25792 KB Output is correct
10 Correct 708 ms 25832 KB Output is correct