oj.uz

Submission #448003

# Submission time Handle Problem Language Result Execution time Memory
448003 2021-07-28T13:18:21 Z rainboy Training (IOI07_training) C
100 / 100
 10 ms 560 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 420 KB Output is correct
2 Correct 3 ms 460 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #7
9.0 / 9.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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 352 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 10 ms 560 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 9 ms 460 KB Output is correct
3 Correct 6 ms 552 KB Output is correct
4 Correct 5 ms 536 KB Output is correct