Submission #64115465

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return a < b ? -1 : a > b;
}
int ec[212345], *es[212345];
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
}
struct syourai_s {
  int to_node;
  int res;
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int cmp_int(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int ec[212345], *es[212345];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

struct syourai_s {
	int to_node;
	int res;
};

/* 最大頂点数の降順 */
int cmp_syourai(const void* x, const void* y) {
	struct syourai_s a = *(const struct syourai_s*)x, b = *(const struct syourai_s*)y;
	return a.res > b.res ? -1 : a.res < b.res;
}

struct syourai_s* syourai[212345];
int *memo[212345];

int get_idx(const int* table, int table_num, int query) {
	int l = 0,r = table_num - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (table[m] == query) return m;
		else if (table[m] < query) l = m + 1;
		else r = m - 1;
	}
	return table_num;
}

int calc(int node, int from) {
	int *pmemo = &memo[node][get_idx(es[node], ec[node], from)];
	int i;
	int ans = 1, cnt = 0, cnt_needed = 3 + (from <= 0);
	if (*pmemo) return ~*pmemo;

	if (syourai[node] == NULL) {
		/* 来た元以外について、頂点数の最大値を求める */
		syourai[node] = malloc(sizeof(*syourai[node]) * ec[node]);
		for (i = 0; i < ec[node]; i++) {
			syourai[node][i].to_node = es[node][i];
			if (es[node][i] == from) {
				syourai[node][i].res = -1;
			} else {
				syourai[node][i].res = calc(es[node][i], node);
			}
		}
		qsort(syourai[node], ec[node], sizeof(*syourai[node]), cmp_syourai);
	} else if (syourai[node][ec[node] - 1].res < 0 && from != syourai[node][ec[node] - 1].to_node) {
		/* 欠けているデータを埋める */
		syourai[node][ec[node] - 1].res = calc(syourai[node][ec[node] - 1].to_node, node);
		qsort(syourai[node], ec[node], sizeof(*syourai[node]), cmp_syourai);
	}
	/* 来た元以外から、必要な分データを多い順に取る */
	for (i = 0; i < ec[node]; i++) {
		if (syourai[node][i].to_node != from) {
			ans += syourai[node][i].res;
			cnt++;
			if (cnt >= cnt_needed) break;
		}
	}
	/* データが足りない場合、最初の場合失格、そうでない場合その頂点だけを使う */
	if (cnt < cnt_needed) ans = from > 0;

	return ~(*pmemo = ~ans);
}

int main(void) {
	int N;
	int i;
	int ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		int A, B;
		if (scanf("%d%d", &A, &B) != 2) return 1;
		ae(A, B);
		ae(B, A);
	}
	for (i = 1; i <= N; i++) {
		if (ec[i] > 0) qsort(es[i], ec[i], sizeof(*es[i]), cmp_int);
		memo[i] = calloc(ec[i] + 1, sizeof(*memo[i]));
	}
	for (i = 1; i <= N; i++) {
		int candidate = calc(i, 0);
		if (candidate > ans) ans = candidate;
	}
	printf("%d\n", ans - (ans == 0));
	return 0;
}

Submission Info

Judge Result