(cache)Submission #70927283 - Educational DP Contest

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

Submission #70927283

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>
int ec[114514], *es[114514];
int memo[114514];
int dfs(int node) {
  int ans = 0, i;
  if (memo[node]) return memo[node] - 1;
  for (i = 0; i < ec[node]; i++) {
    int candidate = dfs(es[node][i]) + 1;
    if (ans < candidate) ans = candidate;
  }
  memo[node] = ans + 1;
  return ans;
}
int main(void) {
  int N, M;
  int ans = 0, i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

int memo[114514];

int dfs(int node) {
	int ans = 0, i;
	if (memo[node]) return memo[node] - 1;
	for (i = 0; i < ec[node]; i++) {
		int candidate = dfs(es[node][i]) + 1;
		if (ans < candidate) ans = candidate;
	}
	memo[node] = ans + 1;
	return ans;
}

int main(void) {
	int N, M;
	int ans = 0, i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int x, y;
		if (scanf("%d%d", &x, &y) != 2) return 1;
		es[x] = realloc(es[x], sizeof(*es[x]) * (ec[x] + 1));
		if (es[x] == NULL) return 2;
		es[x][ec[x]++] = y;
	}
	for (i = 1; i <= N; i++) {
		int candidate = dfs(i);
		if (ans < candidate) ans = candidate;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time	2025-11-15 07:12:47
Task	G - Longest Path
User	mikecat
Language	C (gcc 12.2.0)
Score	100
Code Size	773 Byte
Status	AC
Exec Time	29 ms
Memory	9148 KiB

Judge Result

Set Name

All

Score / Max Score

100 / 100

Status

× 22

Set Name	Test Cases
All	0_00, 0_01, 0_02, 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, 1_16, 1_17, 1_18

Case Name	Status	Exec Time	Memory
0_00	AC	0 ms	1704 KiB
0_01	AC	1 ms	1608 KiB
0_02	AC	0 ms	1616 KiB
1_00	AC	0 ms	1640 KiB
1_01	AC	29 ms	9148 KiB
1_02	AC	13 ms	2404 KiB
1_03	AC	22 ms	5056 KiB
1_04	AC	18 ms	3560 KiB
1_05	AC	17 ms	2912 KiB
1_06	AC	15 ms	2568 KiB
1_07	AC	14 ms	2412 KiB
1_08	AC	15 ms	2148 KiB
1_09	AC	14 ms	2192 KiB
1_10	AC	13 ms	2312 KiB
1_11	AC	17 ms	2548 KiB
1_12	AC	23 ms	4884 KiB
1_13	AC	22 ms	4724 KiB
1_14	AC	17 ms	2776 KiB
1_15	AC	16 ms	2576 KiB
1_16	AC	20 ms	4120 KiB
1_17	AC	23 ms	5584 KiB
1_18	AC	19 ms	3400 KiB