結果
問題 | No.2328 Build Walls |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-28 14:51:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,548 ms / 3,000 ms |
コード長 | 11,622 bytes |
コンパイル時間 | 1,119 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 316,800 KB |
最終ジャッジ日時 | 2024-12-27 03:17:44 |
合計ジャッジ時間 | 24,038 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
from cmath import inffrom re import Mimport sysfrom collections import deque, Counterfrom math import atan2, gcd, log10, pi, sqrt, ceilfrom bisect import bisect, bisect_left, bisect_right, insortfrom typing import Iterable, TypeVar, Union, Tuple, Iterator, List# import bisectfrom decimal import *import fractionsimport timeimport copyimport heapqimport itertoolsimport bisectimport mathimport randomfrom fractions import Fractionfrom functools import lru_cache, partial, cmp_to_keyimport operator# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')# import string# import networkx as nxinput = sys.stdin.readlinesys.setrecursionlimit(10000000)mod = 10 ** 9 + 7mod2 = 998244353# mod = 1 << 128# mod = 10 ** 30 + 1INF = 1 << 61DIFF = 10 ** -9DX = [1, 0, -1, 0, 1, 1, -1, -1]DY = [0, 1, 0, -1, 1, -1, 1, -1]def read_values(): return map(int, input().split())def read_index(): return map(lambda x: int(x) - 1, input().split())def read_list(): return list(read_values())def read_lists(N): return [read_list() for _ in range(N)]class UnionFind:def __init__(self,n):self.parent=list(range(n))self.size=[1]*ndef root(self,a):if(self.parent[a]==a):return aself.parent[a]=self.root(self.parent[a])return self.parent[a]def union(self,a,b):pa=self.root(a)pb=self.root(b)if(pa==pb):returnif(self.size[pa]>self.size[pb]):pa,pb=pb,paself.parent[pa] = pbself.size[pb]+=self.size[pa]def same(self,a,b):return self.root(a)==self.root(b)class Dijkstra:def __init__(self,n):self.dist=[inf]*nself.g = [list() for _ in range(n)]def add(self,u,v,c):self.g[u].append((v,c))def calc(self,s):self.dist[s]=0q = [(0,s)]while(len(q)>0):d,v0 = heapq.heappop(q)if(d>self.dist[v0]):continuefor (v1,c) in self.g[v0]:if(self.dist[v1]<=d+c):continueself.dist[v1]=d+cheapq.heappush(q,(self.dist[v1],v1))class SegTree:def __init__(self,n):self.size=1while(self.size<n):self.size*=2self.d=[self.unit()]*(self.size*2)def unit(self):return 0def calc(self,a,b):return a+bdef set(self,i,v):self.forceset(i+self.size,v)def forceset(self,i,v):self.d[i]=vwhile(i>1):p=i//2self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])i=p#[l,r)def get(self,i):return self.d[self.size+i]def query(self,l,r):return self.queryImpl(l,r,0,self.size,1)def queryImpl(self,l,r,ll,rr,v):if(r<=ll or rr<=l):return self.unit()if(l<=ll and rr<=r):return self.d[v]m = (ll+rr)//2vl = self.queryImpl(l,r,ll,m,v*2+0)vr =self.queryImpl(l,r,m,rr,v*2+1)return self.calc(vl,vr)class LazySegTree:def __init__(self,n):self.size=1while(self.size<n):self.size*=2self.d=[self.unit()]*(self.size*2)self.f=[self.id()]*self.size*2def unit(self):return -10**18def id(self):return -10**18def calc(self,a,b):return max(a,b)def set(self,i,v):self.forceset(i+self.size,v)def forceset(self,i,v):self.d[i]=vwhile(i>1):p=i//2self.d[p]=self.calc(self.d[p*2],self.d[p*2+1])i=p#[l,r)def get(self,i):return self.query(i,i+1)def query(self,l,r):return self.queryImpl(l,r,0,self.size,1)def queryImpl(self,l,r,ll,rr,v):if(r<=ll or rr<=l):return self.unit()self.func(v)if(l<=ll and rr<=r):return self.d[v]m = (ll+rr)//2return self.calc(self.queryImpl(l,r,ll,m,v*2+0),self.queryImpl(l,r,m,rr,v*2+1))def funcSet(self,l,r,fnc):return self.funcSetImpl(l,r,fnc,0,self.size,1)def funcSetImpl(self,l,r,fnc,ll,rr,v):if(r<=ll or rr<=l):returnif(l<=ll and rr<=r):self.comp(v,fnc)self.func(v)self.forceset(v,self.d[v])returnm = (ll+rr)//2self.funcSetImpl(l,r,fnc,ll,m,v*2+0)self.funcSetImpl(l,r,fnc,m,rr,v*2+1)def func(self,i):if(i<self.size):self.comp(i*2+0,self.f[i])self.comp(i*2+1,self.f[i])self.d[i]=max(self.d[i],self.f[i])self.f[i]=self.id()def comp(self,i,fnc):self.f[i]=max(self.f[i],fnc)class BIT:def __init__(self,n):self.siz=1while(self.siz<n):self.siz<<=1self.b=[0]*self.sizdef update(self,k,v):k+=1while(k<=self.siz):self.b[k-1]+=vk+=k&-kdef query(self,k):r = 0k+=1while(k>0):r+=self.b[k-1]k-=k&-kreturn rclass MaxFlow:def __init__(self,n):self.g = [list() for _ in range(n)]self.r = [list() for _ in range(n)]self.f = [list() for _ in range(n)]self.mc=[False]*nself.size=nself.q=[-1]*nself.e=0def add(self,u,v,c):self.g[u].append(v)self.g[v].append(u)self.r[u].append(len(self.f[v]))self.r[v].append(len(self.f[u]))self.f[u].append(c)self.f[v].append(0)self.e+=1def bfs(self,s,t):self.depth=[-2]*self.sizeself.depth[s]=0self.q[0]=sl=0r=1while(l<r):v=self.q[l]l+=1for i in range(len(self.g[v])):v2=self.g[v][i]if(self.depth[v2]==-2 and self.f[v][i]>0):self.depth[v2]=self.depth[v]+1if(v2==t):returnself.q[r]=v2r+=1def dfs(self,v,t,f):if(v==t):return fr=0for i in range(self.pg[v],len(self.g[v])):self.pg[v]=iv2=self.g[v][i]i2=self.r[v][i]if(self.f[v][i]==0 or self.depth[v]+1!=self.depth[v2]):continued=self.dfs(v2,t,min(f-r,self.f[v][i]))if(d==0):continueself.f[v][i]-=dself.f[v2][i2]+=dr+=dif(r==f):breakself.depth[v]=self.sizereturn rdef flow(self,s,t):r=0while(1):self.bfs(s,t)if(self.depth[t]==-2):return rif(self.depth[t]*self.depth[t]*2>self.e):breakself.pg=[0]*self.sizef = self.dfs(s,t,10**18)if(f==0):breakr+=fwhile(1):self.fi=[False]*self.sizef = self.dfs2(s,t,10**18)if(f==0):breakr+=freturn rdef mincut(self,v):self.mc[v]=Truefor i in range(len(self.g[v])):v2,c,i2=self.g[v][i]if(self.mc[v2] or self.f[v][i]==0):continueself.mincut(v2)def extgcd(a,b):if(b==0):return (1,0)u,v=extgcd(b,a%b)return (v,u-a//b*v)def convolution(f,g,m):l=1v=m-1r=vpg=3if (m == 2):pg = 1;if (m == 754974721):pg=11;rpg=pow(pg,m-2,m)p=list()rp=list()while(len(f)+len(g)>l+1):l*=2r//=2p.append(pow(pg,r,m))rp.append(pow(rpg,r,m))while(p[-1]!=1):p.append(p[-1]*p[-1]%m)rp.append(rp[-1]*rp[-1]%m)def FFT(ff,k,pl):fl=len(ff)if(fl==1):return ffhl=fl//2ef=FFT(ff[::2],k+1,pl)of=FFT(ff[1::2],k+1,pl)r=[0]*flmul=1for i in range(hl):r[i+0]=(ef[i]+of[i]*mul)%mr[i+hl]=(ef[i]-of[i]*mul)%mmul=(mul*pl[k])%mreturn rff=[0]*lgg=[0]*lfor i in range(len(f)):ff[i]=f[i]for i in range(len(g)):gg[i]=g[i]ff=FFT(ff,0,p)gg=FFT(gg,0,p)for i in range(l):ff[i]=(ff[i]*gg[i])%ma=FFT(ff,0,rp)rl=pow(l,m-2,m)for i in range(l):a[i]=a[i]*rl%mreturn aclass scc:def __init__(self,n):self.g=[list() for _ in range(n)]self.rg=[list() for _ in range(n)]self.size=ndef add(self,u,v):self.g[u].append(v)self.rg[v].append(u)def calc(self):f=[-1]*self.sizenf=[0]c=[False]*self.sizedef dfs1(v):c[v]=Truefor tv in self.g[v]:if(c[tv]):continuedfs1(tv)f[nf[0]]=vnf[0]+=1for i in range(self.size):if(f[i]!=-1):continuedfs1(i)r=list()c=[False]*self.sizenf[0]=0def dfs2(v):r[nf[0]].append(v)c[v]=Truefor tv in self.rg[v]:if(c[v]):continuedfs1(tv)for i in range(self.size-1,-1,-1):if(c[i]):continuer.append(list())dfs2(i)nf[0]+=1return rdef lower_bound(a,v):l=-1r=len(a)while(l+1<r):m=(l+r)//2if(a[m]<v):l=melse:r=mreturn rclass Bimatching:def __init__(self,n):self.size=nself.g=[[] for _ in range(n)]self.to=[-1]*ndef add(self,u,v):self.g[u].append(v)def calc(self):p=range(self.size)c=[]for i in p:c.append((len(self.g[i]),i))c.sort()pl=[0]*self.sizefor i in p:pl[i]=c[i][1]rev=[-1]*self.sizefr=[-1]*self.sizeq=[0]*self.sizefor i in pl:q[0]=ir=1d=[0]*self.sized[i]=1for l in p:if(l>=r):breakv=q[l]for w in self.g[v]:if(fr[w]!=-1):if(d[fr[w]]==0):d[fr[w]]=1rev[fr[w]]=vq[r]=fr[w]r+=1else:r=0vv=vbw=wfor _ in p:if(bw==-1):breakbw,self.to[vv]=self.to[vv],bwfr[self.to[vv]]=vvvv=rev[vv]breakdef main():h,w=read_values()a=[list() for _ in range(h-2)]for i in range(h-2):a[i]=read_list()dj=Dijkstra((h-2)*w+2)s=(h-2)*wg=s+1d=[(1,-1),(1,0),(1,1),(0,-1),(0,1),(-1,-1),(-1,0),(-1,1)]for i in range(h-2):for j in range(w):for dx,dy in d:nx=i+dxny=j+dyif ny<0 or nx<0 or nx >= h-2:continueif ny==w:dj.add(i*w+j,g,0)else:if(a[nx][ny]<0):continuedj.add(i*w+j,nx*w+ny,a[nx][ny])for i in range(h-2):if(a[i][0]<0):continuedj.add(s,i*w,a[i][0])dj.calc(s)if(dj.dist[g]<10**15):print(dj.dist[g])else:print(-1)if __name__ == "__main__":main()