Submission #674050

#	Time	Username	Problem	Language	Result	Execution time	Memory
674050		rainboy	Designated Cities (JOI19_designated_cities)	C11	100 / 100	1010 ms	38932 KiB

designated_cities

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int ij[(N - 1) * 2], ww[(N - 1) * 2];
int *eh[N], eo[N];

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

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

void remove_(int i, int h) {
	int o;

	for (o = eo[i]; o--; )
		if (eh[i][o] == h) {
			eo[i]--;
			while (o < eo[i])
				eh[i][o] = eh[i][o + 1], o++;
			return;
		}
}

int sz[N], c;

void dfs1(int p, int i, int n) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = ij[h ^ 1];

		if (j != p) {
			dfs1(i, j, n);
			sz[i] += sz[j];
			if (sz[j] * 2 > n)
				centroid = 0;
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c = i;
}

int cc[N], cnt; long long xx[N], xx_[N], ss[N];

void dfs2(int p, int c, int i) {
	int o, j_;

	j_ = -1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = ij[h ^ 1];
		
		if (j != p) {
			dfs2(i, c, j);
			xx[j] += ww[h];
			if (j_ == -1 || xx[j_] < xx[j])
				j_ = j;
		}
	}
	xx[i] = j_ == -1 ? 0 : xx[j_];
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = ij[h ^ 1];
		
		if (j != p && j != j_)
			cc[cnt] = c, xx_[cnt] = xx[j], cnt++;
	}
}

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

		while (j < k)
			if (xx_[gg[j]] == xx_[g])
				j++;
			else if (xx_[gg[j]] > xx_[g]) {
				tmp = gg[i], gg[i] = gg[j], gg[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = gg[j], gg[j] = gg[k], gg[k] = tmp;
			}
		sort(gg, l, i);
		l = k;
	}
}

long long ans[N + 1];

void cd(int i, int n, long long x) {
	static int gg[N];
	int o, g, k;
	long long sum;

	if (n == 1) {
		ans[1] = min(ans[1], x);
		return;
	}
	dfs1(-1, i, n), i = c;
	cnt = 0;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = ij[h ^ 1];

		dfs2(i, j, j);
		cc[cnt] = j, xx_[cnt] = xx[j] + ww[h], cnt++;
	}
	cc[cnt] = i, xx_[cnt] = 0, cnt++;
	for (g = 0; g < cnt; g++)
		ss[cc[g]] = 0;
	sum = 0;
	for (g = 0; g < cnt; g++) {
		sum += xx_[g];
		ss[cc[g]] += xx_[g];
	}
	for (g = 0; g < cnt; g++)
		gg[g] = g;
	sort(gg, 0, cnt);
	for (g = 1; g < cnt; g++)
		if (cc[gg[g]] != cc[gg[g - 1]]) {
			ans[1] = min(ans[1], x += sum);
			x -= xx_[gg[g]];
			for (k = 2; k <= cnt; k++) {
				x -= k <= g + 1 ? xx_[gg[k - 2]] : xx_[gg[k - 1]];
				ans[k] = min(ans[k], x);
			}
			break;
		}
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = ij[h ^ 1];

		remove_(j, h ^ 1);
		cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i], x + sum - ss[j] + ww[h ^ 1]);
	}
}

int main() {
	int n, q, h, i, j, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d%d%d", &i, &j, &ww[h << 1 | 0], &ww[h << 1 | 1]), i--, j--;
		ij[h << 1 | 0] = i, ij[h << 1 | 1] = j;
		append(i, h << 1 | 0), append(j, h << 1 | 1);
	}
	memset(ans, 0x3f, (n + 1) * sizeof *ans);
	cd(0, n, 0);
	for (k = 1; k <= n; k++)
		ans[k] = min(ans[k], ans[k - 1]);
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &k);
		printf("%lld\n", ans[k]);
	}
	return 0;
}

Compilation message (stderr)

designated_cities.c: In function 'append':
designated_cities.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
designated_cities.c: In function 'main':
designated_cities.c:155:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
designated_cities.c:159:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%d%d%d%d", &i, &j, &ww[h << 1 | 0], &ww[h << 1 | 1]), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.c:167:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
designated_cities.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |   scanf("%d", &k);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44