star_leinad's blog

By star_leinad, history, 10 months ago, In English

I was solving this problem, and couldn't find why it's failing at 17.

import sys
import threading
input = sys.stdin.readline
from collections import defaultdict

def main():

    t = int(input())

    for _ in range(t):
        n, k = map(int, input().split())
        costs = list(map(int, input().split()))
        free = list(map(int, input().split()))

        possible = defaultdict(list)

        for node in range(1, n+1):
            possible[node] = list(map(int, input().split()))[1:]
        
        ans = [-1] * n
        for node in free:
            ans[node-1] = 0

        # print(possible)
        def calculate(node):
            if ans[node-1] != -1:
                return ans[node-1]
            
            total = 0
            check = False
            for child in possible[node]:
                total += calculate(child)
                check = True
            
            if check: ans[node-1] = min(total , costs[node-1])
            else: ans[node-1] = costs[node-1]
            return ans[node-1]
        
        for node in range(1, n+1):
            if ans[node-1] == -1:
                calculate(node)
        
        print(*ans)

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()


Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it