#938600 (PyPy3) No.1153 ねこちゃんゲーム

提出ソース

結果

問題	No.1153 ねこちゃんゲーム
ユーザー	vwxyz
提出日時	2023-12-16 02:10:49
言語	PyPy3 (7.3.15)
結果	AC
実行時間	2,415 ms / 2,500 ms
コード長	12,096 bytes
コンパイル時間	533 ms
コンパイル使用メモリ	82,984 KB
実行使用メモリ	323,556 KB
最終ジャッジ日時	2024-09-27 07:10:38
合計ジャッジ時間	73,327 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	36 ms 55,116 KB
testcase_01	AC	36 ms 56,528 KB
testcase_02	AC	103 ms 77,356 KB
testcase_03	AC	91 ms 76,824 KB
testcase_04	AC	105 ms 77,336 KB
testcase_05	AC	95 ms 76,996 KB
testcase_06	AC	100 ms 77,248 KB
testcase_07	AC	2,025 ms 243,844 KB
testcase_08	AC	1,613 ms 240,072 KB
testcase_09	AC	2,004 ms 249,216 KB
testcase_10	AC	1,631 ms 240,880 KB
testcase_11	AC	2,008 ms 243,712 KB
testcase_12	AC	2,004 ms 249,212 KB
testcase_13	AC	1,658 ms 240,508 KB
testcase_14	AC	2,106 ms 248,516 KB
testcase_15	AC	1,685 ms 246,500 KB
testcase_16	AC	2,038 ms 245,500 KB
testcase_17	AC	2,037 ms 248,940 KB
testcase_18	AC	1,627 ms 241,796 KB
testcase_19	AC	2,006 ms 241,896 KB
testcase_20	AC	1,607 ms 243,448 KB
testcase_21	AC	1,982 ms 241,144 KB
testcase_22	AC	2,199 ms 242,684 KB
testcase_23	AC	1,682 ms 242,816 KB
testcase_24	AC	1,925 ms 246,528 KB
testcase_25	AC	1,591 ms 243,828 KB
testcase_26	AC	1,996 ms 240,384 KB
testcase_27	AC	2,415 ms 266,872 KB
testcase_28	AC	1,985 ms 266,464 KB
testcase_29	AC	2,316 ms 267,772 KB
testcase_30	AC	1,934 ms 267,832 KB
testcase_31	AC	2,287 ms 266,620 KB
testcase_32	AC	1,753 ms 320,012 KB
testcase_33	AC	1,573 ms 316,544 KB
testcase_34	AC	1,868 ms 318,844 KB
testcase_35	AC	1,684 ms 317,376 KB
testcase_36	AC	1,873 ms 319,248 KB
testcase_37	AC	1,009 ms 322,740 KB
testcase_38	AC	1,042 ms 323,052 KB
testcase_39	AC	1,118 ms 323,556 KB
testcase_40	AC	990 ms 321,524 KB
testcase_41	AC	1,039 ms 322,300 KB

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

ソースコード

raw source code

import sys
readline=sys.stdin.readline

class Graph:
    def __init__(self,V,edges=None,graph=None,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if graph!=None:
            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 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):
        assert self.subtree or 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

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=[[None]*self.N for k in range(self.k)]
        for n in range(self.N):
            self.permutation_doubling[0][n]=self.permutation[n]
        if self.lst!=None:
            self.doubling=[[None]*self.N for k in range(self.k)]
            for n in range(self.N):
                self.doubling[0][n]=self.lst[n]
        for k in range(1,self.k):
            for n in range(self.N):
                if self.permutation_doubling[k-1][n]!=None:
                    self.permutation_doubling[k][n]=self.permutation_doubling[k-1][self.permutation_doubling[k-1][n]]
                    if self.f!=None:
                        self.doubling[k][n]=self.f(self.doubling[n][k-1],self.doubling[k-1][self.permutation_doubling[k-1][n]])

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

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

    def Bisect(self,x,is_ok):
        if not is_ok(x):
            return -1,None
        K=0
        for k in range(self.k-1,-1,-1):
            if is_ok(self.permutation_doubling[k][x]):
                K|=1<<k
                x=self.permutation_doubling[k][x]
        return K,x

N,M=map(int,readline().split())
A=list(map(int,readline().split()))
for m in range(M):
    A[m]-=1
edges=[]
for n in range(N-1):
    u,v=map(int,readline().split())
    u-=1;v-=1
    edges.append((u,v))
G=Graph(N,edges=edges)
def f(x,merged_a):
    g=0
    while g in merged_a:
        g+=1
    return {g}
def f_merge(x,lst):
    retu=set()
    for se in lst:
        retu|=se
    return retu
G.Build_Rerooting(0,f,f_merge,subtree=True)
gr=0
grundy=[list(G.Rerooting(x,x))[0] for x in range(N)]
for a in A:
    gr^=grundy[a]
if gr:
    seen=[False]*N
    for m in range(M):
        x=A[m]
        if seen[x]:
            continue
        seen[x]=True
        for y in G.graph[x]:
            if gr==grundy[x]^list(G.Rerooting(x,y))[0]:
                i,v=m+1,y+1
else:
    i,v=-1,-1
print(i,v)

yukicoder

結果

テストケース

ソースコード