結果
問題 | No.2020 Sum of Common Prefix Length |
ユーザー | vwxyz |
提出日時 | 2023-08-11 05:19:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,263 ms / 2,000 ms |
コード長 | 14,077 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 361,204 KB |
最終ジャッジ日時 | 2024-04-28 22:11:09 |
合計ジャッジ時間 | 27,050 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
55,296 KB |
testcase_01 | AC | 49 ms
55,040 KB |
testcase_02 | AC | 43 ms
54,784 KB |
testcase_03 | AC | 145 ms
78,988 KB |
testcase_04 | AC | 145 ms
78,864 KB |
testcase_05 | AC | 145 ms
79,040 KB |
testcase_06 | AC | 146 ms
78,756 KB |
testcase_07 | AC | 560 ms
114,508 KB |
testcase_08 | AC | 720 ms
114,440 KB |
testcase_09 | AC | 505 ms
114,376 KB |
testcase_10 | AC | 497 ms
114,912 KB |
testcase_11 | AC | 515 ms
114,604 KB |
testcase_12 | AC | 505 ms
114,912 KB |
testcase_13 | AC | 511 ms
114,980 KB |
testcase_14 | AC | 516 ms
114,820 KB |
testcase_15 | AC | 612 ms
135,868 KB |
testcase_16 | AC | 621 ms
136,624 KB |
testcase_17 | AC | 769 ms
213,652 KB |
testcase_18 | AC | 712 ms
185,300 KB |
testcase_19 | AC | 728 ms
185,172 KB |
testcase_20 | AC | 1,041 ms
319,988 KB |
testcase_21 | AC | 1,225 ms
306,680 KB |
testcase_22 | AC | 1,251 ms
306,428 KB |
testcase_23 | AC | 1,204 ms
304,140 KB |
testcase_24 | AC | 1,242 ms
321,240 KB |
testcase_25 | AC | 1,263 ms
317,964 KB |
testcase_26 | AC | 608 ms
233,356 KB |
testcase_27 | AC | 43 ms
54,528 KB |
testcase_28 | AC | 568 ms
122,712 KB |
testcase_29 | AC | 560 ms
123,316 KB |
testcase_30 | AC | 572 ms
122,528 KB |
testcase_31 | AC | 1,024 ms
344,828 KB |
testcase_32 | AC | 1,012 ms
361,204 KB |
testcase_33 | AC | 719 ms
256,336 KB |
testcase_34 | AC | 695 ms
162,900 KB |
testcase_35 | AC | 717 ms
163,016 KB |
testcase_36 | AC | 771 ms
261,804 KB |
testcase_37 | AC | 779 ms
207,440 KB |
ソースコード
import sys readline=sys.stdin.readline class Node: def __init__(self,parent,e,i): self.parent=parent self.children={} self.value=e self.cnt=0 self.i=i def Parent(self): return self.parent def __getitem__(self,x): return self.children[x] class Trie: def __init__(self,e=None): self.e=e self.root=Node(None,self.e,0) self.node_cnt=1 def __getitem__(self,key): node=self.root for x in key: if not x in node.children: return self.e node=node[x] return node.value def __setitem__(self,key,value): node=self.root for x in key: if not x in node.children: node.children[x]=Node(node,self.e,self.node_cnt) self.node_cnt+=1 node=node[x] if node.value==self.e: node=self.root node.cnt+=1 for x in key: node=node[x] node.cnt+=1 node.value=value def __delitem__(self,key): node=self.root for x in key: if not x in node.children: return node=node[x] node=self.root node.cnt-=1 for x in key: node=node[x] node.cnt-=1 node.value=self.e def __contains__(self,key): node=self.root for x in key: if not x in node.children: return False node=node[x] return True def __len__(self): return self.root.cnt def Nodes(self): queue=[self.root] retu=[] while queue: node=queue.pop() retu.append(node) for x,node in node.children.items(): queue.append(node) return retu 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 class Segment_Tree: def __init__(self,N,f,e,lst=None,dynamic=False): self.f=f self.e=e self.N=N if dynamic: self.segment_tree=defaultdict(lambda:self.e) else: if lst==None: self.segment_tree=[self.e]*2*self.N else: assert len(lst)<=self.N self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst)) for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def __getitem__(self,i): if type(i)==int: if -self.N<=i<0: return self.segment_tree[i+self.N*2] elif 0<=i<self.N: return self.segment_tree[i+self.N] else: raise IndexError("list index out of range") else: a,b,c=i.start,i.stop,i.step if a==None: a=self.N else: a+=self.N if b==None: b=self.N*2 else: b+=self.N return self.segment_tree[slice(a,b,c)] def __setitem__(self,i,x): if -self.N<=i<0: i+=self.N*2 elif 0<=i<self.N: i+=self.N else: raise IndexError("list index out of range") self.segment_tree[i]=x while i>1: i>>= 1 self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Build(self,lst): for i,x in enumerate(lst,self.N): self.segment_tree[i]=x for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Fold(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N vL=self.e vR=self.e while L<R: if L&1: vL=self.f(vL,self.segment_tree[L]) L+=1 if R&1: R-=1 vR=self.f(self.segment_tree[R],vR) L>>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N if L==R: return None x=self.Fold(L-self.N,R-self.N) while L<R: if L&1: if self.segment_tree[L]==x: i=L break L+=1 if R&1: R-=1 if self.segment_tree[R]==x: i=R break L>>=1 R>>=1 while i<self.N: if self.segment_tree[i]==self.segment_tree[i<<1]: i<<=1 else: i<<=1 i|=1 i-=self.N return i def Bisect_Right(self,L=None,f=None): if L==self.N: return self.N if L==None: L=0 L+=self.N vl=self.e vr=self.e l,r=L,self.N*2 while l<r: if l&1: vl=self.f(vl,self.segment_tree[l]) l+=1 if r&1: r-=1 vr=self.f(self.segment_tree[r],vr) l>>=1 r>>=1 if f(self.f(vl,vr)): return self.N v=self.e while True: while L%2==0: L>>=1 vv=self.f(v,self.segment_tree[L]) if f(vv): v=vv L+=1 else: while L<self.N: L<<=1 vv=self.f(v,self.segment_tree[L]) if f(vv): v=vv L+=1 return L-self.N def Bisect_Left(self,R=None,f=None): if R==0: return 0 if R==None: R=self.N R+=self.N vl=self.e vr=self.e l,r=self.N,R while l<r: if l&1: vl=self.f(vl,self.segment_tree[l]) l+=1 if r&1: r-=1 vr=self.f(self.segment_tree[r],vr) l>>=1 r>>=1 if f(self.f(vl,vr)): return 0 v=self.e while True: R-=1 while R>1 and R%2: R>>=1 vv=self.f(self.segment_tree[R],v) if f(vv): v=vv else: while R<self.N: R=2*R+1 vv=self.f(self.segment_tree[R],v) if f(vv): v=vv R-=1 return R+1-self.N def __str__(self): return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]" N=int(readline()) S=[readline().rstrip() for n in range(N)] SS=[list(s) for s in S] Q=int(readline()) query=[] for q in range(Q): lst=readline().split() if lst[0]=="1": _,x,c=lst x=int(x)-1 SS[x]+=[c] query.append((1,x,c)) else: _,x=lst x=int(x)-1 query.append((2,x)) Tr=Trie(0) for s in SS: Tr[s]=0 nodes=Tr.Nodes() edges=[] le=len(nodes) for n0 in nodes: for x,n1 in n0.children.items(): edges.append((n0.i,n1.i)) G=Graph(le,edges=edges) tour=G.SIV_DFS(0,euler_tour=True) idx_in=[None]*le idx_out=[None]*le for i in range(2*le): if tour[i]>=0: idx_in[tour[i]]=i else: idx_out[~tour[i]]=i ST=Segment_Tree(2*le,lambda x,y:x+y,0) node=[Tr.root]*N for i in range(N): for s in S[i]: node[i]=node[i].children[s] ST[idx_in[node[i].i]]+=1 ST[idx_out[node[i].i]]-=1 for tpl in query: if tpl[0]==1: _,x,c=tpl node[x]=node[x][c] i=node[x].i ST[idx_in[i]]+=1 ST[idx_out[i]]-=1 else: _,x=tpl i=node[x].i ans=ST.Fold(0,idx_in[i]+1) print(ans)