제출 #376617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376617		rainboy	Beads and wires (APIO14_beads)	C11	0 / 100	1 ms	364 KiB

beads

#include <stdio.h>
#include <stdlib.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][2];

void dfs(int p, int c_, int i) {
	int o, x0, x1, x2;

	x0 = 0, x1 = -1, x2 = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], c = ec[i][o];

		if (j != p) {
			dfs(i, c, j);
			x2 = max(x2 == -1 ? -1 : x2 + dp[j][0], x1 == -1 ? -1 : x1 + dp[j][1]);
			x1 = max(x1 == -1 ? -1 : x1 + dp[j][0], x0 + dp[j][1]);
			x0 += dp[j][0];
		}
	}
	dp[i][0] = max(max(x0, x2), x1 == -1 ? -1 : x1 + c_), dp[i][1] = max(x0, x2) + 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", dp[0][1]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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