제출 #762787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762787		rainboy	Bread First Search (CCO21_day2problem2)	C11	25 / 25	59 ms	14792 KiB

Main

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

#define N	200000

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

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

void append(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 main() {
	static char used[N];
	static int jj[N], kk[N], dp[N + 1], dq[N + 1];
	int n, m, h, i, j, j_, k, o, tmp;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		if (i > j)
			tmp = i, i = j, j = tmp;
		append(i, j);
	}
	for (i = 0, j_ = -1, k = 0; i < n; i++) {
		if (used[i])
			k--;
		j_ = max(j_, i + 1);
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (!used[j])
				used[j] = 1, k++;
			j_ = max(j_, j);
		}
		jj[i] = j_, kk[i] = k;
	}
	dp[n - 1] = dq[n - 1] = 0;
	for (i = n - 2; i >= 0; i--) {
		dp[i] = kk[i] + dq[jj[i]];
		dq[i] = max(dq[i + 1], dp[i]);
	}
	printf("%d\n", n - 1 - dp[0]);
	return 0;
}

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

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

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 14 / 14