(cache)Submission #71041286 - Educational DP Contest

Contest Duration: 2019-01-06(Sun) 20:00 - 2019-01-07(Mon) 01:00 (local time) (300 minutes)

Submission #71041286

Source Code Expand

Copy

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>
#define MOD_BY 1000000007
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return (int)((long long)a * b % MOD_BY);
}
int ec[114514], *es[114514];
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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MOD_BY 1000000007

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

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

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;
}

int memo[114514][2];

int calc(int node, int parent, int is_kuro) {
	int ans = 1;
	int i;
	if (memo[node][is_kuro]) return ~memo[node][is_kuro];
	/* 白 */
	for (i = 0; i < ec[node]; i++) {
		int next = es[node][i];
		if (next != parent) ans = mul(ans, calc(next, node, 0));
	}
	/* 黒 */
	if (!is_kuro) {
		int ans2 = 1;
		for (i = 0; i < ec[node]; i++) {
			int next = es[node][i];
			if (next != parent) ans2 = mul(ans2, calc(next, node, 1));
		}
		ans = add(ans, ans2);
	}
	return ~(memo[node][is_kuro] = ~ans);
}

int main(void) {
	int N, i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		int x, y;
		if (scanf("%d%d", &x, &y) != 2) return 1;
		ae(x, y);
		ae(y, x);
	}
	printf("%d\n", calc(1, 0, 0));
	return 0;
}

Submission Info

Submission Time	2025-11-18 06:53:07
Task	P - Independent Set
User	mikecat
Language	C (gcc 12.2.0)
Score	100
Code Size	1164 Byte
Status	AC
Exec Time	41 ms
Memory	13624 KiB

Judge Result

Set Name

All

Score / Max Score

100 / 100

Status

× 20

Set Name	Test Cases
All	0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15

Case Name	Status	Exec Time	Memory
0_00	AC	1 ms	1668 KiB
0_01	AC	1 ms	1660 KiB
0_02	AC	1 ms	1624 KiB
0_03	AC	1 ms	1548 KiB
1_00	AC	1 ms	1620 KiB
1_01	AC	41 ms	13624 KiB
1_02	AC	22 ms	7052 KiB
1_03	AC	24 ms	7272 KiB
1_04	AC	31 ms	7816 KiB
1_05	AC	31 ms	7756 KiB
1_06	AC	31 ms	7424 KiB
1_07	AC	30 ms	6972 KiB
1_08	AC	31 ms	6732 KiB
1_09	AC	32 ms	6740 KiB
1_10	AC	32 ms	6572 KiB
1_11	AC	33 ms	6544 KiB
1_12	AC	34 ms	6500 KiB
1_13	AC	33 ms	6988 KiB
1_14	AC	34 ms	8548 KiB
1_15	AC	41 ms	10788 KiB