When taking min, you should only consider the propagated fun value of the
direct child, not the accumulated sum.
You also need to increase the recursion depth to avoid runtime error.
See the accepted code below:
*import syssys.setrecursionlimit(200000)memo = {}#recursivity on node from
abyss to triggerable nodesdef compute_path_fun(graph, elem, memo): if
elem in memo: return memo[elem] else: a = max(funs[elem],
min([compute_path_fun(graph,el, memo)[0] for el in graph[elem]])) b
= sum([memo[el][1] + memo[el][0] for el in graph[elem]]) - min([memo[el][0]
for el in graph[elem]]) memo[elem] = [a, b] return memo[elem]
T = int(input())for t in range(T): N = int(input()) F = list(map(int,
input().split())) P = list(map(int, input().split())) funs = {k:v
for k,v in zip(range(1,N+1), F)} graph = {k:[] for k in range(N+1)}
for node in range(len(P)): graph[P[node]].append(node+1) # dico
of previous element in graph #initialization of the memo with
triggerable nodes (no previous node) memo = {k:[funs[k], 0] for k in
graph.keys() if graph[k] == [] and k!=0} # we build path from abyss to
triggerable nodes out = sum([compute_path_fun(graph, el, memo)[0] +
compute_path_fun(graph, el, memo)[1] for el in graph[0]])
print(f"Case #{t+1}: {out}")*
在2022年4月5日星期二 UTC-7 17:26:30<thierry...@gmail.com> 写道：
> Hello everyone,
>
> I tried to solve the chain reaction problem using dynamic programming with
> recursivity.
> *My logic*:
> I considered a graph that I built using dictionary where the key is the
> node number and the value is a list of nodes that point to the key node.
> The Abyss is my node number 0. So key with [ ] as value are
> trigerrable nodes.
> My recursivity starts from abyss to trigerrable nodes. So, the final score
> would be the abyss's fun score.
> I passed the sample test but got WA. Could anyone tell me what's wrong
> with my code please?
> My code in attachment
>
> Thank you in advance
> Thierry
>
>
>
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
google-code@googlegroups.com. To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
---
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/101a65db-9974-435b-a16e-68988d5a8f19n%40googlegroups.com.
