#842467 (PyPy3) No.1333 Squared Sum

提出ソース
結果

問題	No.1333 Squared Sum
ユーザー	vwxyz
提出日時	2023-02-22 16:27:46
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	22,426 bytes
コンパイル時間	424 ms
コンパイル使用メモリ	82,336 KB
実行使用メモリ	269,628 KB
最終ジャッジ日時	2024-07-22 18:06:50
合計ジャッジ時間	62,763 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	41 ms 56,448 KB
testcase_01	AC	42 ms 56,192 KB
testcase_02	AC	42 ms 56,832 KB
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	AC	1,876 ms 254,340 KB
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	AC	40 ms 56,192 KB
testcase_17	AC	42 ms 56,704 KB
testcase_18	AC	43 ms 56,576 KB
testcase_19	AC	43 ms 56,320 KB
testcase_20	AC	41 ms 56,192 KB
testcase_21	AC	41 ms 56,448 KB
testcase_22	AC	41 ms 56,448 KB
testcase_23	AC	42 ms 56,576 KB
testcase_24	AC	42 ms 56,064 KB
testcase_25	AC	42 ms 56,064 KB
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	AC	1,012 ms 142,488 KB
testcase_31	AC	678 ms 116,208 KB
testcase_32	AC	1,450 ms 177,648 KB
testcase_33	AC	1,147 ms 154,792 KB
testcase_34	AC	1,948 ms 214,892 KB
testcase_35	AC	1,443 ms 178,492 KB
testcase_36	AC	919 ms 131,572 KB
testcase_37	AC	966 ms 134,280 KB
testcase_38	AC	1,069 ms 147,472 KB
testcase_39	AC	1,648 ms 190,692 KB
testcase_40	AC	1,940 ms 264,648 KB
testcase_41	AC	1,944 ms 263,064 KB
testcase_42	AC	1,934 ms 264,992 KB
testcase_43	AC	1,925 ms 261,708 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import sys
readline=sys.stdin.readline

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

    def MIV_DFS(self,initial_vertices=None,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):
        if initial_vertices==None:
            initial_vertices=[s for s in range(self.V)]
        seen=[False]*self.V
        finished=[False]*self.V
        if bipartite_graph:
            bg=[None]*self.V
            cnt=-1
        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 bipartite_graph or unweighted_dist:
            uwd=[self.inf]*self.V
        if weighted_dist:
            wd=[self.inf]*self.V
        for s in initial_vertices:
            if seen[s]:
                continue
            if bipartite_graph:
                cnt+=1
                bg[s]=(cnt,0)
            if linked_components:
                lc.append([])
            if bipartite_graph or unweighted_dist:
                uwd[s]=0
            if weighted_dist:
                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[-1].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 bipartite_graph:
                                bg[y]=(cnt,bg[x][1]^1)
                            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 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_=bg
            bg=[[[],[]] for i in range(cnt+1)]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if not bg_[i][1]^bg_[j][1]:
                    bg[bg_[i][0]]=False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].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

    def SIV_BFS(self,s,bfs_tour=False,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        seen[s]=True
        if bfs_tour:
            bt=[s]
        if linked_components:
            lc=[s]
        if parents:
            ps=[None]*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
        queue=deque([s])
        while queue:
            x=queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    y,d=y
                if not seen[y]:
                    seen[y]=True
                    queue.append(y)
                    if bfs_tour:
                        bt.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y]=x
                    if unweighted_dist or bipartite_graph:
                        uwd[y]=uwd[x]+1
                    if weighted_dist:
                        wd[y]=wd[x]+d
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if uwd[i]==self.inf or uwd[j]==self.inf:
                    continue
                if not uwd[i]%2^uwd[j]%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 bfs_tour:
            retu+=(bt,)
        if bipartite_graph:
            retu+=(bg,)
        if linked_components:
            retu+=(lc,)
        if parents:
            retu+=(ps,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu

    def MIV_BFS(self,initial_vertices=None,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):
        if initial_vertices==None:
            initial_vertices=[i for i in range(self.V)]
        seen=[False]*self.V
        if bipartite_graph:
            bg=[None]*self.V
            cnt=-1
        if linked_components:
            lc=[]
        if parents:
            ps=[None]*self.V
        if unweighted_dist:
            uwd=[self.inf]*self.V
        if weighted_dist:
            wd=[self.inf]*self.V
        for s in initial_vertices:
            if seen[s]:
                continue
            seen[s]=True
            if bipartite_graph:
                cnt+=1
                bg[s]=(cnt,0)
            if linked_components:
                lc.append([s])
            if unweighted_dist:
                uwd[s]=0
            if weighted_dist:
                wd[s]=0
            queue=deque([s])
            while queue:
                x=queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        seen[y]=True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y]=(cnt,bg[x][1]^1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y]=x
                        if unweighted_dist:
                            uwd[y]=uwd[x]+1
                        if weighted_dist:
                            wd[y]=wd[x]+d
        if bipartite_graph:
            bg_=bg
            bg=[[[],[]] for i in range(cnt+1)]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if not bg_[i][1]^bg_[j][1]:
                    bg[bg_[i][0]]=False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        retu=()
        if bipartite_graph:
            retu+=(bg,)
        if linked_components:
            retu+=(lc,)
        if parents:
            retu=(ps,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu

    def Build_Approach(self,s):
        self.approach_parents,self.approach_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True)
        self.approach_parents[s]=s
        self.approach_PD=Path_Doubling(self.V,self.approach_parents)
        self.approach_PD.Build_Next()

    def Approach(self,x,y):
        if x==y:
            return None
        if self.approach_depth[x]>=self.approach_depth[y]:
            return self.approach_parents[x]
        retu=self.approach_PD.Permutation_Doubling(y,self.approach_depth[y]-self.approach_depth[x]-1)
        if self.approach_parents[retu]==x:
            return retu
        else:
            return self.approach_parents[x]

    def Build_Rerooting(self,s,f,f_merge,subtree=False):
        self.rerooting_s=s
        self.rerooting_f=f
        self.rerooting_f_merge=f_merge
        self.subtree=subtree
        if self.subtree:
            parents,postorder,preorder,self.rerooting_depth=self.SIV_DFS(s,parents=True,postorder=True,preorder=True,unweighted_dist=True)
            parents[s]=s
            self.rerooting_PD=Path_Doubling(self.V,parents)
            self.rerooting_PD.Build_Next()
            parents[s]=None
        else:
            parents,postorder,preorder=self.SIV_DFS(s,parents=True,postorder=True,preorder=True)
        self.rerooting_lower_dp=[None]*self.V
        for x in postorder:
            children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]]
            self.rerooting_lower_dp[x]=self.rerooting_f_merge(x,[self.rerooting_f(y,self.rerooting_lower_dp[y]) for y in children])
        self.rerooting_upper_dp=[None]*self.V
        for x in preorder:
            children=[y[0] if self.weighted else y for y in self.graph[x] if (y[0] if self.weighted else y)!=parents[x]]
            left_accumule_f=[None]*(len(children)+1)
            right_accumule_f=[None]*(len(children)+1)
            left_accumule_f[0]=self.rerooting_f_merge(x,[])
            for i in range(1,len(children)+1):
                left_accumule_f[i]=self.rerooting_f_merge(x,[left_accumule_f[i-1],self.rerooting_f(children[i-1],self.rerooting_lower_dp[children[i-1]])])
            right_accumule_f[len(children)]=self.rerooting_f_merge(x,[])
            for i in range(len(children)-1,-1,-1):
                right_accumule_f[i]=self.rerooting_f_merge(x,[right_accumule_f[i+1],self.rerooting_f(children[i],self.rerooting_lower_dp[children[i]])])
            for i in range(len(children)):
                if parents[x]==None:
                    self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1]]))
                else:
                    self.rerooting_upper_dp[children[i]]=self.rerooting_f(x,self.rerooting_f_merge(x,[left_accumule_f[i],right_accumule_f[i+1],self.rerooting_upper_dp[x]]))
        if self.subtree:
            self.rerooting_parents=parents

    def Rerooting(self,root,subtree=None):
        if self.subtree and root!=subtree:
            if self.rerooting_depth[subtree]>=self.rerooting_depth[root]:
                x=self.rerooting_parents[subtree]
            else:
                x=self.rerooting_PD.Permutation_Doubling(root,self.rerooting_depth[root]-self.rerooting_depth[subtree]-1)
                if self.rerooting_parents[x]!=subtree:
                    x=self.rerooting_parents[subtree]
            if self.rerooting_parents[subtree]==x:
                retu=self.rerooting_f(subtree,self.rerooting_lower_dp[subtree])
            else:
                retu=self.rerooting_upper_dp[x]
        else:
            if root==self.rerooting_s:
                retu=self.rerooting_f(root,self.rerooting_lower_dp[root])
            else:
                retu=self.rerooting_f(root,self.rerooting_f_merge(root,[self.rerooting_lower_dp[root],self.rerooting_upper_dp[root]]))
        return retu

def XOR_Basis(lst):
    xor_basis=[]
    triangulation=[]
    for i,x in enumerate(lst):
        xx=x
        for j,xb in enumerate(triangulation):
            if xx>xx^xb:
                xx=xx^xb
        if xx:
            xor_basis.append(x)
            for j in range(len(triangulation)):
                if triangulation[j]^xx<triangulation[j]:
                    triangulation[j]^=xx
            triangulation.append(xx)
    return xor_basis,triangulation

class Path_Doubling:
    def __init__(self,N,permutation,lst=None,f=None,e=None):
        self.N=N
        self.permutation=permutation
        self.lst=lst
        self.f=f
        self.e=e

    def Build_Next(self,K=None):
        if K==None:
            K=self.N
        self.k=K.bit_length()
        self.permutation_doubling=[[self.permutation[n]] for n in range(self.N)]
        if self.lst!=None:
            self.doubling=[[self.lst[n]] for n in range(self.N)]
        for i in range(1,self.k):
            for n in range(self.N):
                self.permutation_doubling[n].append(self.permutation_doubling[self.permutation_doubling[n][i-1]][i-1])
                if self.f!=None:
                    self.doubling[n].append(self.f(self.doubling[n][i-1],self.doubling[self.permutation_doubling[n][i-1]][i-1]))

    def Permutation_Doubling(self,N,K):
        if K<0:
            return N
        for i in range(self.k):
            if K>>i&1:
                N=self.permutation_doubling[N][i]
        return N

    def Doubling(self,N,K):
        if K<0:
            return self.e
        retu=self.e
        for i in range(self.k):
            if K>>i&1:
                retu=self.f(retu,self.doubling[N][i])
                N=self.permutation_doubling[N][i]
        return retu

N=int(readline())
edges=[]
W={}
for n in range(N-1):
    u,v,w=map(int,readline().split())
    u-=1;v-=1
    edges.append((u,v,w))
    W[(u,v)]=w
    W[(v,u)]=w
mod=10**9+7
def f(x,tpl):
    d0,d1,d2=tpl
    return x,d0+1,d1,d2
def f_merge(x,lst):
    D0,D1,D2=0,0,0
    for tpl in lst:
        if len(tpl)==3:
            d0,d1,d2=tpl
            D0+=d0
            D1+=d1
            D2+=d2
        else:
            y,d0,d1,d2=tpl
            w=W[(x,y)]
            D0+=d0
            D1+=d1+w*d0%mod
            D2+=d2+2*d1*w%mod+w*w*d0%mod
    return D0,D1,D2
G=Graph(N,edges=edges,weighted=True)
G.Build_Rerooting(0,f,f_merge)
ans=0
for x in range(N):
    ans+=G.Rerooting(x)[3]
inve2=(1+mod)//2
ans*=inve2
ans%=mod
print(ans)
yukicoder

結果

テストケース

ソースコード
