#713695 (PyPy3) No.348 カゴメカゴメ

提出ソース

結果

問題	No.348 カゴメカゴメ
ユーザー	vwxyz
提出日時	2021-11-06 02:50:27
言語	PyPy3 (7.3.15)
結果	AC
実行時間	936 ms / 2,000 ms
コード長	14,915 bytes
コンパイル時間	995 ms
コンパイル使用メモリ	82,780 KB
実行使用メモリ	244,156 KB
最終ジャッジ日時	2024-11-06 20:07:56
合計ジャッジ時間	20,599 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	811 ms 161,696 KB
testcase_01	AC	85 ms 77,364 KB
testcase_02	AC	936 ms 244,156 KB
testcase_03	AC	718 ms 155,008 KB
testcase_04	AC	111 ms 78,208 KB
testcase_05	AC	96 ms 77,952 KB
testcase_06	AC	55 ms 59,648 KB
testcase_07	AC	55 ms 58,880 KB
testcase_08	AC	52 ms 59,008 KB
testcase_09	AC	57 ms 60,672 KB
testcase_10	AC	55 ms 60,032 KB
testcase_11	AC	55 ms 60,032 KB
testcase_12	AC	130 ms 78,976 KB
testcase_13	AC	109 ms 77,824 KB
testcase_14	AC	98 ms 77,696 KB
testcase_15	AC	797 ms 162,376 KB
testcase_16	AC	53 ms 59,392 KB
testcase_17	AC	54 ms 59,008 KB
testcase_18	AC	52 ms 58,880 KB
testcase_19	AC	54 ms 59,264 KB
testcase_20	AC	68 ms 70,400 KB
testcase_21	AC	60 ms 60,288 KB
testcase_22	AC	55 ms 59,264 KB
testcase_23	AC	878 ms 149,416 KB
testcase_24	AC	898 ms 149,060 KB
testcase_25	AC	889 ms 147,784 KB
testcase_26	AC	934 ms 149,792 KB
testcase_27	AC	883 ms 146,480 KB
testcase_28	AC	874 ms 146,508 KB
testcase_29	AC	860 ms 145,880 KB
testcase_30	AC	865 ms 148,032 KB
testcase_31	AC	883 ms 146,584 KB
testcase_32	AC	874 ms 146,984 KB
testcase_33	AC	231 ms 83,200 KB
testcase_34	AC	227 ms 82,944 KB
testcase_35	AC	230 ms 82,944 KB
testcase_36	AC	230 ms 83,200 KB
testcase_37	AC	228 ms 82,944 KB
testcase_38	AC	228 ms 83,200 KB
testcase_39	AC	226 ms 83,456 KB
testcase_40	AC	226 ms 83,012 KB
testcase_41	AC	228 ms 83,336 KB
testcase_42	AC	229 ms 83,200 KB
testcase_43	AC	132 ms 78,336 KB
testcase_44	AC	127 ms 78,376 KB
testcase_45	AC	127 ms 78,208 KB
testcase_46	AC	128 ms 78,208 KB
testcase_47	AC	129 ms 78,080 KB
testcase_48	AC	121 ms 77,824 KB
testcase_49	AC	134 ms 77,952 KB
testcase_50	AC	130 ms 77,824 KB
testcase_51	AC	130 ms 77,952 KB
testcase_52	AC	124 ms 77,948 KB

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

ソースコード

raw source code

import random
import heapq
from collections import defaultdict,deque
import sys
readline=sys.stdin.readline

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n

    def Find(self,x):
        stack=[]
        while self.parents[x]>=0:
            stack.append(x)
            x=self.parents[x]
        for y in stack:
            self.parents[y]=x
        return x

    def Union(self,x,y):
        x=self.Find(x)
        y=self.Find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def Size(self,x):
        return -self.parents[self.Find(x)]

    def Same(self,x,y):
        return self.Find(x)==self.Find(y)

    def Members(self,x):
        root = self.Find(x)
        return [i for i in range(self.n) if self.Find(i)==root]

    def Roots(self):
        return [i for i, x in enumerate(self.parents) if x<0]

    def Group_Count(self):
        return len(self.Roots())

    def All_Group_Members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.Find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.All_Group_Members().items())

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        if not graph:
            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)
        else:
            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))

    def SS_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=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 parents or cycle_detection or subtree_size:
            ps=[None]*self.V
            ps[s]=s
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        if subtree_size:
            ss=[1]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[float('inf')]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[float('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 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 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 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:
                i,j=tpl[:2] if self.weighted else tpl
                if type(uwd[i])==float or type(uwd[j])==float:
                    continue
                if not uwd[i]%2^uwd[j]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x])==float:
                        continue
                    bg[uwd[x]%2].append(x)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            tpl+=(cd,)
        if directed_acyclic:
            tpl+=(dag,)
        if euler_tour:
            tpl+=(et,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if postorder:
            tpl+=(post,)
        if preorder:
            tpl+=(pre,)
        if subtree_size:
            tpl+=(ss,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            tpl+=(tp_sort,)
        if unweighted_dist:
            tpl+=(uwd,)
        if weighted_dist:
            tpl+=(wd,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def AP_DFS(self,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,topological_sort=False):
        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 parents or cycle_detection:
            ps=[None]*self.V
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        for s in range(self.V):
            if seen[s]:
                continue
            if bipartite_graph:
                cnt+=1
                bg[s]=(cnt,0)
            if linked_components:
                lc.append([])
            if parents:
                ps[s]=s
            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 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:
                                ps[y]=x
                        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 postorder or topological_sort:
                        post.append(x)
        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)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            tpl+=(cd,)
        if directed_acyclic:
            tpl+=(dag,)
        if euler_tour:
            tpl+=(et,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if postorder:
            tpl+=(post,)
        if preorder:
            tpl+=(pre,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            tpl+=(tp_sort,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def Build_Hash(self,s,random_number=False,mod=False,rerooting=False):
        self.bottom_hash=[None]*self.V
        if random_number:
            self.hash_random_number=random_number
        else:
            self.hash_random_number=[random.randint(1,10**10) for i in range(self.V)]
        if mod:
            self.hash_mod=mod
        else:
            self.hash_mod=(1<<61)-1
        parents,postorder,preorder=self.SS_DFS(s,parents=True,postorder=True,preorder=True)
        for x in postorder:
            level=0
            for y in self.graph[x]:
                if y==parents[x]:
                    continue
                h,l=self.bottom_hash[y]
                level=max(level,l+1)
            ha=1
            for y in self.graph[x]:
                if y==parents[x]:
                    continue
                h,l=self.bottom_hash[y]
                ha*=h+self.hash_random_number[l]
                ha%=self.hash_mod
            self.bottom_hash[x]=(ha,level)
        if rerooting:
            self.top_hash=[None]*self.V
            self.top_hash[s]=(1,0)
            for x in preorder:
                children=[y for y in self.graph[x] if y!=parents[x]]
                if children:
                    l=len(children)
                    l_lst,r_lst=[None]*(l+1),[None]*(l+1)
                    l_lst[0],r_lst[l]=(1,-1),(1,-1)
                    for i in range(1,l+1):
                        h0,l0=l_lst[i-1]
                        h1,l1=self.bottom_hash[children[i-1]]
                        l_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1))
                    for i in range(l-1,-1,-1):
                        h0,l0=r_lst[i+1]
                        h1,l1=self.bottom_hash[children[i]]
                        r_lst[i]=(h0*(h1+self.hash_random_number[l1])%self.hash_mod,max(l0,l1))
                    for i in range(l):
                        if x==s:
                            ha,level=1,0
                        else:
                            ha,level=self.top_hash[x]
                        h0,l0=l_lst[i]
                        h1,l1=r_lst[i+1]
                        ha*=h0*h1
                        level=max(level,l0+1,l1+1)
                        ha+=self.hash_random_number[level]
                        ha%=self.hash_mod
                        level+=1
                        self.top_hash[children[i]]=(ha,level)
        return 

    def Hash(self,root,subtree=False):
        if subtree:
            ha,level=self.bottom_hash[root]
            ha+=self.hash_random_number[level]
            ha%=self.hash_mod
        else:
            h0,l0=self.bottom_hash[root]
            h1,l1=self.top_hash[root]
            ha=(h0*h1+self.hash_random_number[max(l0,l1)])%self.hash_mod
            level=max(l0,l1)
        return ha,level

N,M=map(int,readline().split())
grid=["."*(M+2)]+["."+readline().rstrip()+"." for i in range(N)]+["."*(M+2)]
N+=2;M+=2
UF=UnionFind(N*M)
for n in range(N):
    for m in range(M):
        for dn,dm in ((0,1),(1,0)):
            if 0<=n+dn<N and 0<=m+dm<M and grid[n][m]==grid[n+dn][m+dm]:
                UF.Union(n*M+m,(n+dn)*M+(m+dm))
        for dn,dm in ((1,1),(1,-1)):
            if 0<=n+dn<N and 0<=m+dm<M and grid[n][m]=="x" and grid[n+dn][m+dm]=="x":
                UF.Union(n*M+m,(n+dn)*M+(m+dm))
lc=list(UF.All_Group_Members().values())
l=len(lc)
idx=[None]*(N*M)
for i in range(l):
    for x in lc[i]:
        idx[x]=i
queue=[idx[0]]
seen=[False]*l
seen[idx[0]]=True
edges=[]
while queue:
    i=queue.pop()
    for x in lc[i]:
        n,m=divmod(x,M)
        for dn,dm in ((1,0),(0,1)):
            if 0<=n+dn<N and 0<=m+dm<M and idx[n*M+m]!=idx[(n+dn)*M+(m+dm)] and not seen[idx[(n+dn)*M+(m+dm)]]:
                queue.append(idx[(n+dn)*M+(m+dm)])
                seen[idx[(n+dn)*M+(m+dm)]]=True
                edges.append((idx[n*M+m],idx[(n+dn)*M+(m+dm)]))
G=Graph(l,edges=edges)
bg,parents=G.SS_DFS(idx[0],bipartite_graph=True,parents=True)
for lst in bg:
    if not idx[0] in lst:
        lst.append(idx[0])
        break
dct={x:i for i,x in enumerate(lst)}
edges=[]
for x in lst:
    if x==idx[0]:
        continue
    if parents[x]==idx[0]:
        edges.append((dct[x],dct[parents[x]]))
    else:
        edges.append((dct[x],dct[parents[parents[x]]]))
strength=[len(lc[x]) if x!=idx[0] else 0 for x in lst]
root=dct[idx[0]]
l=len(edges)+1
G=Graph(l,edges=edges)
parents,postorder=G.SS_DFS(root,parents=True,postorder=True)
dp0,dp1=[0]*l,[0]*l
for x in postorder:
    dp1[x]+=strength[x]
    for y in G.graph[x]:
        if y==parents[x]:
            continue
        dp1[x]+=dp0[y]
        dp0[x]+=max(dp0[y],dp1[y])
ans=max(dp0[root],dp1[root])
print(ans)

yukicoder

結果

テストケース

ソースコード