結果

問題 No.3283 Labyrinth and Friends
コンテスト
ユーザー navel_tos
提出日時 2025-09-27 12:18:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 1,547 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 77,336 KB
最終ジャッジ日時 2025-09-27 12:18:22
合計ジャッジ時間 4,585 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3283 Labyrinth and Friends

def main():
    #入力受取
    input = __import__('sys').stdin.readline
    N, X = map(int, input().split())
    P = [0] * N
    Gin = [0] * N
    C, S = [0] * N, [0] * N
    for now, v in enumerate(input().split(), start = 1):
        nxt = int(v) - 1
        P[now] = nxt
        Gin[nxt] += 1
        C[now], S[now] = map(int, input().split())
        
    #DP[now][s]: 頂点nowと連続する子を解放した上で、ステータスをちょうどsとする最小コスト
    Ssum = S[:]
    Q = [now for now, Gin_now in enumerate(Gin) if Gin_now == 0]
    for now in Q:
        if now == 0: break
        nxt = P[now]
        Gin[nxt] -= 1
        if Gin[nxt] == 0:
            Q.append(nxt)
        Ssum[nxt] += Ssum[now]
    DP = [[0x7FFFFFFFFFFFFFFF] * (Ssum_now + 1) for Ssum_now in Ssum]
    for now, S_now in enumerate(S):
        Ssum[now] = S_now
        DP[now][S[now]] = C[now]

    #二乗の木DP  インラインに更新する
    for now in Q:
        if now == 0:
            break
        nxt = P[now]
        dp_now, dp_nxt = DP[now], DP[nxt]
        for s in range(Ssum[nxt], -1, -1):
            if (dp_nxt_s := dp_nxt[s]) == 0x7FFFFFFFFFFFFFFF:
                continue
            for s_t, dp_now_t in enumerate(dp_now, start = s):
                if dp_now_t != 0x7FFFFFFFFFFFFFFF and dp_nxt[s_t] > dp_nxt_s + dp_now_t:
                    dp_nxt[s_t] = dp_nxt_s + dp_now_t
        Ssum[nxt] += Ssum[now]
            
    #答えを出力
    print(min(DP[0][X:]))


main()
0