Submission #448003

#	Time	Username	Problem	Language	Result	Execution time	Memory
448003		rainboy	Training (IOI07_training)	C11	100 / 100	10 ms	560 KiB

training

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

#define N	1000
#define M	5000
#define K	10

int max(int a, int b) { return a > b ? a : b; }

int *ej[N], eo[N], *eh[N], eo_[N];
int uu[M], vv[M], cc[M];

void append(int **ej, int *eo, 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;
}

int pp[N], dd[N];

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

	pp[i] = p, dd[i] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs1(i, j, d + 1);
	}
}

int lca(int i, int j) {
	while (i != j)
		if (dd[i] > dd[j])
			i = pp[i];
		else
			j = pp[j];
	return i;
}

int jj[N], hh[N], dp[N], dq[N], dr[1 << K];

void dfs2(int p, int i) {
	int o, k, b, b_, h, x;

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

		if (j != p)
			dfs2(i, j);
	}
	k = 0, x = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			jj[hh[j] = k++] = j;
			x += dp[j];
		}
	}
	memset(dr, -1, (1 << k) * sizeof *dr), dr[0] = x;
	for (o = eo_[i]; o--; ) {
		int h = eh[i][o], u = uu[h], v = vv[h];

		b_ = 0, x = cc[h];
		if (u != i) {
			x += dp[u];
			while (pp[u] != i)
				x += dq[u], u = pp[u];
			x -= dp[u];
			b_ |= 1 << hh[u];
		}
		if (v != i) {
			x += dp[v];
			while (pp[v] != i)
				x += dq[v], v = pp[v];
			x -= dp[v];
			b_ |= 1 << hh[v];
		}
		for (b = 0; b < 1 << k; b++)
			if (dr[b] != -1 && (b & b_) == 0)
				dr[b | b_] = max(dr[b | b_], dr[b] + x);
	}
	for (b = 0; b < 1 << k; b++)
		if (dr[b] != -1) {
			dp[i] = max(dp[i], dr[b]);
			for (h = 0; h < k; h++)
				if ((b & 1 << h) == 0) {
					int j = jj[h];

					dq[j] = max(dq[j], dr[b] - dp[j]);
				}
		}
}

int main() {
	int n, m, h, i, sum;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	sum = 0;
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &uu[h], &vv[h], &cc[h]), uu[h]--, vv[h]--;
		if (cc[h] == 0)
			append(ej, eo, uu[h], vv[h]), append(ej, eo, vv[h], uu[h]);
		else
			sum += cc[h];
	}
	dfs1(-1, 0, 0);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++)
		if ((dd[uu[h]] + dd[vv[h]]) % 2 == 0)
			append(eh, eo_, lca(uu[h], vv[h]), h);
	memset(dp, -1, n * sizeof *dp), memset(dq, -1, n * sizeof *dq);
	dfs2(-1, 0);
	printf("%d\n", sum - dp[0]);
	return 0;
}

Compilation message (stderr)

training.c: In function 'append':
training.c:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
training.c: In function 'main':
training.c:103:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
training.c:108:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   scanf("%d%d%d", &uu[h], &vv[h], &cc[h]), uu[h]--, vv[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9