Submission #376645

#	Time	Username	Problem	Language	Result	Execution time	Memory
376645		rainboy	Beads and wires (APIO14_beads)	C11	100 / 100	216 ms	28012 KiB

beads

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

#define N	200000

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

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

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

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

int dp[N][4];

void dfs(int p, int c_, int i) {
	static int dp_[3][3];
	int o, k, t;

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

		if (j != p)
			dfs(i, c, j);
	}
	memset(dp_, -1, sizeof dp_), dp_[0][0] = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			for (k = 2; k >= 0; k--)
				for (t = 2; t >= 0; t--) {
					int x = dp_[k][t];

					if (x == -1)
						continue;
					if (dp[j][0] != -1)
						dp_[k][t] = x + dp[j][0];
					if (k < 2 && dp[j][1] != -1)
						dp_[k + 1][t] = max(dp_[k + 1][t], x + dp[j][1]);
					if (t == 0) {
						if (dp[j][2] != -1)
							dp_[k][1] = max(dp_[k][1], x + dp[j][2]);
						if (k < 2 && dp[j][3] != -1)
							dp_[k + 1][2] = max(dp_[k + 1][2], x + dp[j][3]);
					}
				}
	}
	dp[i][0] = dp_[1][0];
	if (dp[i][0] != -1)
		dp[i][0] += c_;
	dp[i][0] = max(dp[i][0], dp_[0][0]);
	dp[i][1] = dp_[0][0];
	if (dp[i][1] != -1)
		dp[i][1] += c_;
	dp[i][2] = dp_[1][2];
	if (dp[i][2] != -1)
		dp[i][2] += c_;
	dp[i][2] = max(dp[i][2], max(dp_[0][1], max(dp_[2][0], dp_[2][2])));
	dp[i][3] = max(dp_[0][1], max(dp_[2][0], dp_[2][2]));
	if (dp[i][3] != -1)
		dp[i][3] += c_;
}

int main() {
	int n, h, i, j, c;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ec[i] = (int *) malloc(2 * sizeof *ec[i]);
	}
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d%d", &i, &j, &c), i--, j--;
		append(i, j, c), append(j, i, c);
	}
	dfs(-1, 0, 0);
	printf("%d\n", max(dp[0][1], dp[0][3]));
	return 0;
}

Compilation message (stderr)

beads.c: In function 'append':
beads.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
beads.c: In function 'main':
beads.c:75:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   75 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
beads.c:81:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   81 |   scanf("%d%d%d", &i, &j, &c), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43