oj.uz

Submission #393893

# Submission time Handle Problem Language Result Execution time Memory
393893 2021-04-24T19:06:33 Z rainboy Ideal city (IOI12_city) C
100 / 100
 80 ms 9028 KB 
#include <stdlib.h>

#define N	100000
#define MD	1000000000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *xx1, *yy1;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = xx1[ii[j]] != xx1[i_] ? xx1[ii[j]] - xx1[i_] : yy1[ii[j]] - yy1[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int *ej[N], eo[N], sz[N];

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

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

void dfs(int p, int i) {
	int o;

	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs(i, j);
			sz[i] += sz[j];
		}
	}
}

int solve(int *xx, int *yy, int n) {
	static int ii[N], ii_[N];
	int n_, i, j, prev, ans;

	for (i = 0; i < n; i++)
		ii[i] = i;
	xx1 = xx, yy1 = yy, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0, sz[i] = 0;
	for (i = 0, j = 0, prev = 0, n_ = 0; j < n; j++) {
		if (j == 0 || xx[ii[j]] != xx[ii[j - 1]] || yy[ii[j]] != yy[ii[j - 1]] + 1)
			prev = 0, n_++;
		sz[ii_[j] = n_ - 1]++;
		while (i < n && (xx[ii[i]] + 1 < xx[ii[j]] || xx[ii[i]] + 1 == xx[ii[j]] && yy[ii[i]] < yy[ii[j]]))
			i++;
		if (xx[ii[i]] + 1 == xx[ii[j]] && yy[ii[i]] == yy[ii[j]]) {
			if (!prev)
				append(ii_[i], ii_[j]), append(ii_[j], ii_[i]), prev = 1;
		} else
			prev = 0;
	}
	dfs(-1, 0);
	ans = 0;
	for (i = 0; i < n_; i++)
		ans = (ans + (long long) sz[i] * (n - sz[i])) % MD;
	for (i = 0; i < n; i++)
		free(ej[i]);
	return ans;
}

int DistanceSum(int n, int *xx, int *yy) {
	return (solve(xx, yy, n) + solve(yy, xx, n)) % MD;
}

Compilation message

city.c: In function 'append':
city.c:41:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   41 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
city.c: In function 'solve':
city.c:72:76: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |   while (i < n && (xx[ii[i]] + 1 < xx[ii[j]] || xx[ii[i]] + 1 == xx[ii[j]] && yy[ii[i]] < yy[ii[j]]))
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1516 KB Output is correct
2 Correct 13 ms 1620 KB Output is correct
3 Correct 35 ms 3516 KB Output is correct
4 Correct 35 ms 3488 KB Output is correct
5 Correct 70 ms 6640 KB Output is correct
6 Correct 71 ms 6600 KB Output is correct
7 Correct 74 ms 6720 KB Output is correct
8 Correct 69 ms 6596 KB Output is correct
9 Correct 75 ms 6924 KB Output is correct
10 Correct 70 ms 9028 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1660 KB Output is correct
2 Correct 17 ms 1908 KB Output is correct
3 Correct 37 ms 3900 KB Output is correct
4 Correct 35 ms 3992 KB Output is correct
5 Correct 77 ms 7492 KB Output is correct
6 Correct 74 ms 7620 KB Output is correct
7 Correct 76 ms 7620 KB Output is correct
8 Correct 80 ms 7548 KB Output is correct
9 Correct 71 ms 7400 KB Output is correct
10 Correct 71 ms 7328 KB Output is correct