Submission #393893

#	Time	Username	Problem	Language	Result	Execution time	Memory
393893		rainboy	Ideal city (IOI12_city)	C11	100 / 100	80 ms	9028 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45