結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | vwxyz |
提出日時 | 2021-10-23 14:05:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,095 ms / 3,000 ms |
コード長 | 26,339 bytes |
コンパイル時間 | 405 ms |
コンパイル使用メモリ | 81,948 KB |
実行使用メモリ | 154,764 KB |
最終ジャッジ日時 | 2024-09-25 05:08:16 |
合計ジャッジ時間 | 28,413 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 777 ms
154,764 KB |
testcase_01 | AC | 147 ms
88,608 KB |
testcase_02 | AC | 339 ms
92,220 KB |
testcase_03 | AC | 291 ms
91,964 KB |
testcase_04 | AC | 302 ms
91,676 KB |
testcase_05 | AC | 291 ms
92,012 KB |
testcase_06 | AC | 324 ms
92,036 KB |
testcase_07 | AC | 1,095 ms
150,224 KB |
testcase_08 | AC | 1,026 ms
145,952 KB |
testcase_09 | AC | 910 ms
146,280 KB |
testcase_10 | AC | 909 ms
146,284 KB |
testcase_11 | AC | 924 ms
146,520 KB |
testcase_12 | AC | 913 ms
150,396 KB |
testcase_13 | AC | 908 ms
145,116 KB |
testcase_14 | AC | 924 ms
147,508 KB |
testcase_15 | AC | 923 ms
147,704 KB |
testcase_16 | AC | 937 ms
146,460 KB |
testcase_17 | AC | 1,063 ms
150,144 KB |
testcase_18 | AC | 973 ms
147,780 KB |
testcase_19 | AC | 926 ms
146,216 KB |
testcase_20 | AC | 939 ms
148,300 KB |
testcase_21 | AC | 942 ms
147,648 KB |
testcase_22 | AC | 1,021 ms
150,032 KB |
testcase_23 | AC | 987 ms
146,676 KB |
testcase_24 | AC | 976 ms
146,380 KB |
testcase_25 | AC | 1,033 ms
146,840 KB |
testcase_26 | AC | 907 ms
146,264 KB |
testcase_27 | AC | 764 ms
150,388 KB |
testcase_28 | AC | 729 ms
147,928 KB |
testcase_29 | AC | 732 ms
148,388 KB |
ソースコード
import bisect import copy import decimal import fractions import functools import heapq import itertools import math import random import sys from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines 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_BFS(self,s,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V seen[s]=True if linked_components: lc=[s] if parents: ps=[None]*self.V ps[s]=s 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 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 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 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 linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if unweighted_dist: tpl+=(uwd,) if weighted_dist: tpl+=(wd,) if len(tpl)==1: tpl=tpl[0] return tpl def AP_BFS(self,bipartite_graph=False,linked_components=False,parents=False): seen=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if linked_components: lc=[] if parents: ps=[None]*self.V for s in range(self.V): if seen[s]: continue seen[s]=True if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([s]) if parents: ps[s]=s 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 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 linked_components: tpl+=(lc,) if parents: tpl+=(ps,) if len(tpl)==1: tpl=tpl[0] return tpl 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 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 Tree_Diameter(self,weighted=False): def Farthest_Point(u): dist=self.SS_BFS(u,weighted_dist=True) if weighted else self.SS_BFS(u,unweighted_dist=True) fp=0 for i in range(self.V): if dist[fp]<dist[i]: fp=i return fp,dist[fp] u,d=Farthest_Point(0) v,d=Farthest_Point(u) return u,v,d def SCC(self): reverse_graph=[[] for i in range(self.V)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl reverse_graph[j].append(i) postorder=self.AP_DFS(postorder=True) scc=[] seen=[False]*self.V for s in postorder[::-1]: if seen[s]: continue queue=deque([s]) seen[s]=True lst=[] while queue: x=queue.popleft() lst.append(x) for y in reverse_graph[x]: if self.weighted: y=y[0] if not seen[y]: seen[y]=True queue.append(y) scc.append(lst) return scc def Build_LCA(self,s): self.euler_tour,self.parents,depth=self.SS_DFS(s,euler_tour=True,parents=True,unweighted_dist=True) self.dfs_in_index=[None]*self.V self.dfs_out_index=[None]*self.V for i,x in enumerate(self.euler_tour): if x>=0: self.dfs_in_index[x]=i else: self.dfs_out_index[~x]=i self.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),float('inf')) lst=[None]*2*self.V for i in range(2*self.V): if self.euler_tour[i]>=0: lst[i]=depth[self.euler_tour[i]] else: lst[i]=depth[self.parents[~self.euler_tour[i]]] self.ST.Build(lst) def LCA(self,a,b): m=min(self.dfs_in_index[a],self.dfs_in_index[b]) M=max(self.dfs_in_index[a],self.dfs_in_index[b]) x=self.euler_tour[self.ST.Fold_Index(m,M+1)] if x>=0: return x else: return self.parents[~x] def Dijkstra(self,s,route_restoration=False): dist=[float('inf')]*self.V dist[s]=0 hq=[(0,s)] if route_restoration: parents=[None]*self.V parents[s]=s while hq: dx,x=heapq.heappop(hq) if dist[x]<dx: continue for y,dy in self.graph[x]: if dist[y]>dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(hq,(dist[y],y)) if route_restoration: return dist,parents else: return dist def Bellman_Ford(self,s,route_restoration=False): dist=[float('inf')]*self.V dist[s]=0 if route_restoration: parents=[s]*self.V for _ in range(self.V-1): for i,j,d in self.edges: if dist[j]>dist[i]+d: dist[j]=dist[i]+d if route_restoration: parents[j]=i if not self.directed and dist[i]>dist[j]+d: dist[i]=dist[j]+d if route_restoration: parents[i]=j negative_cycle=[] for i,j,d in self.edges: if dist[j]>dist[i]+d: negative_cycle.append(j) if not self.directed and dist[i]>dist[j]+d: negative_cycle.append(i) if negative_cycle: is_negative_cycle=[False]*self.V for i in negative_cycle: if is_negative_cycle[i]: continue else: queue=deque([i]) is_negative_cycle[i]=True while queue: x=queue.popleft() for y,d in self.graph[x]: if not is_negative_cycle[y]: queue.append(y) is_negative_cycle[y]=True if route_restoration: parents[y]=x for i in range(self.V): if is_negative_cycle[i]: dist[i]=-float('inf') if route_restoration: return dist,parents else: return dist def Warshall_Floyd(self,route_restoration=False): dist=[[float('inf')]*self.V for i in range(self.V)] for i in range(self.V): dist[i][i]=0 if route_restoration: parents=[[j for j in range(self.V)] for i in range(self.V)] for i,j,d in self.edges: if dist[i][j]>d: dist[i][j]=d if route_restoration: parents[i][j]=i if not self.directed and dist[j][i]>d: dist[j][i]=d if route_restoration: parents[j][i]=j for k in range(self.V): for i in range(self.V): for j in range(self.V): if dist[i][j]>dist[i][k]+dist[k][j]: dist[i][j]=dist[i][k]+dist[k][j] if route_restoration: parents[i][j]=parents[k][j] for i in range(self.V): if dist[i][i]<0: for j in range(self.V): if dist[i][j]!=float('inf'): dist[i][j]=-float('inf') if route_restoration: return dist,parents else: return dist def Route_Restoration(self,s,g,parents): route=[g] while s!=g and parents[g]!=g: g=parents[g] route.append(g) route=route[::-1] return route def Kruskal(self): UF=UnionFind(self.V) sorted_edges=sorted(self.edges,key=lambda x:x[2]) minimum_spnning_tree=[] for i,j,d in sorted_edges: if not UF.Same(i,j): UF.Union(i,j) minimum_spnning_tree.append((i,j,d)) return minimum_spnning_tree def Ford_Fulkerson(self,s,t): max_flow=0 residual_graph=[defaultdict(int) for i in range(self.V)] if self.weighted: for i,j,d in self.edges: if not d: continue residual_graph[i][j]+=d if not self.directed: residual_graph[j][i]+=d else: for i,j in self.edges: residual_graph[i][j]+=1 if not self.directed: residual_graph[j][i]+=1 while True: parents=[None]*self.V parents[s]=s seen=[False]*self.V seen[s]=True queue=deque([s]) while queue: x=queue.popleft() for y in residual_graph[x].keys(): if not seen[y]: seen[y]=True queue.append(y) parents[y]=x if y==t: tt=t while tt!=s: residual_graph[parents[tt]][tt]-=1 residual_graph[tt][parents[tt]]+=1 if not residual_graph[parents[tt]][tt]: residual_graph[parents[tt]].pop(tt) tt=parents[tt] max_flow+=1 break else: continue break else: break return max_flow def BFS(self,s): seen=[False]*self.V seen[s]=True 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) return def DFS(self,s): seen=[False]*self.V finished=[False]*self.V 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) 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) elif not finished[x]: finished[x]=True return class Segment_Tree: def __init__(self,N,f,e,lst=None): self.f=f self.e=e self.N=N 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 or a<-self.N: a=self.N elif self.N<=a: a=self.N*2 elif a<0: a+=self.N*2 else: a+=self.N if b==None or self.N<=b: b=self.N*2 elif b<-self.N: b=self.N elif b<0: 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 or L<-self.N: L=self.N elif self.N<=L: L=self.N*2 elif L<0: L+=self.N*2 else: L+=self.N if R==None or self.N<=R: R=self.N*2 elif R<-self.N: R=self.N elif R<0: 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 or L<-self.N: L=self.N elif self.N<=L: L=self.N*2 elif L<0: L+=self.N*2 else: L+=self.N if R==None or self.N<=R: R=self.N*2 elif R<-self.N: R=self.N elif R<0: 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 __str__(self): return '['+', '.join(map(str,self.segment_tree[self.N:]))+']' N=int(readline()) edges=[] for i in range(N-1): u,v,w=map(int,readline().split()) edges.append((u,v,w)) G=Graph(N,edges=edges,weighted=True) postorder,dist=G.SS_DFS(0,postorder=True,weighted_dist=True) G.Build_LCA(0) idx=[None]*N for i in range(N): idx[postorder[i]]=i Q=int(readline()) for i in range(Q): X=list(map(int,readline().split())) k,X=X[0],X[1:] X.sort(key=lambda x:idx[x]) ans=0 for i in range(k): x0,x1=X[i],X[(i+1)%k] ans+=dist[x0]+dist[x1]-2*dist[G.LCA(x0,x1)] ans//=2 print(ans)