#759258 (Python3) No.196 典型DP (1)

提出ソース

結果

問題	No.196 典型DP (1)
ユーザー	vwxyz
提出日時	2022-05-08 16:15:21
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	TLE
実行時間	-
コード長	7,274 bytes
コンパイル時間	401 ms
コンパイル使用メモリ	11,480 KB
実行使用メモリ	39,920 KB
最終ジャッジ日時	2023-09-22 12:52:27
合計ジャッジ時間	42,709 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 10,856 KB
testcase_01	AC	34 ms 10,900 KB
testcase_02	AC	35 ms 10,848 KB
testcase_03	AC	35 ms 10,916 KB
testcase_04	AC	36 ms 10,932 KB
testcase_05	AC	34 ms 10,864 KB
testcase_06	AC	34 ms 11,032 KB
testcase_07	AC	34 ms 10,844 KB
testcase_08	AC	34 ms 10,948 KB
testcase_09	AC	34 ms 10,900 KB
testcase_10	AC	35 ms 10,924 KB
testcase_11	AC	36 ms 11,036 KB
testcase_12	AC	36 ms 10,920 KB
testcase_13	AC	36 ms 10,880 KB
testcase_14	AC	36 ms 10,948 KB
testcase_15	AC	69 ms 11,080 KB
testcase_16	AC	172 ms 11,324 KB
testcase_17	AC	341 ms 11,640 KB
testcase_18	AC	628 ms 12,328 KB
testcase_19	AC	771 ms 12,508 KB
testcase_20	AC	1,078 ms 12,408 KB
testcase_21	AC	1,107 ms 12,688 KB
testcase_22	AC	1,076 ms 12,684 KB
testcase_23	AC	1,222 ms 39,920 KB
testcase_24	AC	1,206 ms 31,336 KB
testcase_25	AC	1,225 ms 28,472 KB
testcase_26	AC	993 ms 28,984 KB
testcase_27	AC	1,031 ms 29,044 KB
testcase_28	AC	1,010 ms 29,004 KB
testcase_29	AC	1,017 ms 28,936 KB
testcase_30	AC	1,012 ms 29,032 KB
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	AC	1,150 ms 11,848 KB
testcase_38	TLE	-
testcase_39	TLE	-
testcase_40	TLE	-
testcase_41	AC	35 ms 10,892 KB
testcase_42	AC	34 ms 10,960 KB
testcase_43	AC	34 ms 10,840 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if graph:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))
        else:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        finished=[False]*self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag=True
        if euler_tour:
            et=[]
        if linked_components:
            lc=[]
        if lowlink:
            order=[None]*self.V
            ll=[None]*self.V
            idx=0
        if parents or cycle_detection or lowlink or subtree_size:
            ps=[None]*self.V
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        if subtree_size:
            ss=[1]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[self.inf]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[self.inf]*self.V
            wd[s]=0
        stack=[(s,0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                x,d=stack.pop()
            else:
                x=stack.pop()
            if not seen[x]:
                seen[x]=True
                stack.append((x,d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x]=idx
                    ll[x]=idx
                    idx+=1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        stack.append((y,d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y]=x
                        if unweighted_dist or bipartite_graph:
                            uwd[y]=uwd[x]+1
                        if weighted_dist:
                            wd[y]=wd[x]+d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag=False
                            if cycle_detection:
                                cd=(y,x)
            elif not finished[x]:
                finished[x]=True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl=True
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if ps[x]==y and bl:
                            bl=False
                            continue
                        ll[x]=min(ll[x],order[y])
                    if x!=s:
                        ll[ps[x]]=min(ll[ps[x]],ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if y==ps[x]:
                            continue
                        ss[x]+=ss[y]
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                x,y=tpl[:2] if self.weighted else tpl
                if uwd[x]==self.inf or uwd[y]==self.inf:
                    continue
                if not uwd[x]%2^uwd[y]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if uwd[x]==self.inf:
                        continue
                    bg[uwd[x]%2].append(x)
        retu=()
        if bipartite_graph:
            retu+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            retu+=(cd,)
        if directed_acyclic:
            retu+=(dag,)
        if euler_tour:
            retu+=(et,)
        if linked_components:
            retu+=(lc,)
        if lowlink:
            retu=(ll,)
        if parents:
            retu+=(ps,)
        if postorder:
            retu+=(post,)
        if preorder:
            retu+=(pre,)
        if subtree_size:
            retu+=(ss,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            retu+=(tp_sort,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu

N,K=map(int,readline().split())
edges=[]
for _ in range(N-1):
    a,b=map(int,readline().split())
    edges.append((a,b))
mod=10**9+7
G=Graph(N,edges=edges)
parents,tour=G.SIV_DFS(0,parents=True,postorder=True)
dp=[None]*N
for x in tour:
    dp[x]=[1]
    for y in G.graph[x]:
        if y==parents[x]:
            continue
        prev=dp[x]
        dp[x]=[0]*(len(prev)+len(dp[y])-1)
        for i in range(len(prev)):
            for j in range(len(dp[y])):
                dp[x][i+j]+=prev[i]*dp[y][j]
                dp[x][i+j]%=mod
    dp[x].append(1)
ans=dp[0][K]
print(ans)

yukicoder

結果

テストケース

ソースコード