結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2021-03-18 06:45:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,374 ms / 4,000 ms |
コード長 | 22,171 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 82,536 KB |
実行使用メモリ | 176,076 KB |
最終ジャッジ日時 | 2024-11-16 00:26:25 |
合計ジャッジ時間 | 32,320 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
class Graph:def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):self.n = nself.directed = directedself.decrement = decrementself.destroy = destroyself.edges = [set() for _ in range(self.n)]self.parent = [-1]*self.nfor x, y in edges:self.add_edge(x,y)def add_edge(self, x, y):if self.decrement:x -= 1y -= 1self.edges[x].add(y)if self.directed == False:self.edges[y].add(x)def add_adjacent_list(self, i, adjacent_list):if self.decrement:self.edges[i] = set(map(lambda x: x - 1, adjacent_list))else:self.edges[i] = set(adjacent_list)def bfs(self, start=None, goal=-1, time=0, save=False):""":param start: スタート地点:param goal: ゴール地点:param save: True = 前回の探索結果を保持する:return: (ループがあっても)最短距離。存在しなければ -1"""if start is None: start=self.decrementstart,goal=start-self.decrement,goal-self.decrementif not save:self.parent = [-1] * self.np, t = start, timeself.parent[p] = -2next_set = deque([(p, t)])if p==goal:return twhile next_set:p, t = next_set.popleft()for q in self.edges[p]:if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """continueif self.parent[q] != -1:""" サイクル時の処理 """continueif q == goal:self.parent[q]=preturn t + 1self.parent[q] = pnext_set.append((q, t + 1))return -1def connection_counter(self):""":return: 連結成分の個数。有効グラフではあまり意味がない。"""cnt = 0self.parent = [-1] * self.nfor start in range(self.n):if self.parent[start] == -1:cnt += 1self.bfs(start + self.decrement, save=True)return cntdef connection_detail(self):""":return: 連結成分の(頂点数, 辺の数)。有効グラフではあまり意味がない。備考: 木であるための必要十分条件は M=N-1"""ver_edge=[]self.parent = [-1] * self.nfor start in range(self.n):if self.parent[start] == -1:ver_cnt, edge_cnt = self._detail(start + self.decrement)ver_edge.append((ver_cnt, edge_cnt))return ver_edgedef _detail(self, start=None):""":param start: スタート地点:param save: True = 前回の探索結果を保持する"""if start is None: start=self.decrementstart=start-self.decrementp, t = start, 0self.parent[p] = -2next_set = deque([(p, t)])sub_edges,sub_vers = set(),set()while next_set:p, t = next_set.popleft()sub_vers.add(p)for q in self.edges[p]:if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """continuesub_edges.add((min(p,q),max(p,q)))if self.parent[q] != -1:""" サイクル時の処理 """continueself.parent[q] = pnext_set.append((q, t + 1))return len(sub_vers),len(sub_edges)def distance_list(self, start=None, save=False):""":param start: スタート地点:return: スタート地点から各点への距離のリスト※ 距離無限大が -1 になっている点に注意!!!"""dist = [-1]*self.nif start is None: start=self.decrementstart=start-self.decrementif not save:self.parent = [-1] * self.np, t = start, 0self.parent[p] = -2dist[p] = 0next_set = deque([(p, t)])while next_set:p, t = next_set.popleft()for q in self.edges[p]:if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """continueif self.parent[q] != -1:""" サイクル時の処理 """continuedist[q] = t + 1self.parent[q] = pnext_set.append((q, t + 1))return distdef parent_list(self, start=None):""":return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号訪問しない場合は -1 を返す"""if start is None: start=self.decrementself.distance_list(start)return list(p + self.decrement for p in self.parent[1:])def most_distant_point(self, start=None, save=False):"""計算量 O(N):return: (start から最も遠い頂点, 距離)"""if not save:self.parent = [-1] * self.nif start is None: start=self.decrementstart=start-self.decrementres = (start, 0)temp = 0for i, dist in enumerate(self.distance_list(start+self.decrement, save=save)):if dist > temp:temp = distres = (i + self.decrement, dist)return resdef diameter(self, save=False):"""計算量 O(N):return: 木の直径(最も離れた二頂点間の距離)を返す"""if not save:self.parent = [-1] * self.np = self.most_distant_point(save=save)res = self.most_distant_point(start=p[0], save=save)return res[1]def all_cycle(self):"""無向グラフ用 O(V(V+E))"""res=[]for start in range(self.n):flg=0self.parent = [-1] * self.np, t = start, 0self.parent[p] = -2next_set=deque()starts=set()for q in self.edges[p]:next_set.append((q, t))self.parent[q]=pstarts.add(q)while next_set and flg==0:p, t = next_set.popleft()for q in self.edges[p]:if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """continueif self.parent[q] != -1:""" サイクル時の処理 """if q in starts:cycle=[q+self.decrement]r=pwhile r not in starts:cycle.append(r+self.decrement)r=self.parent[r]if r<0: return -1cycle.append(r+self.decrement)cycle.append(start+self.decrement)res.append(cycle[::-1])flg=1breakcontinueself.parent[q] = pnext_set.append((q, t + 1))return resdef minimum_cycle_directed(self):"""有向グラフ用 O(V(V+E))"""INF=10**18dist=[]history=[]for i in range(self.n):dist.append(self.distance_list(start=i+self.decrement,save=False,INF=INF)[:])history.append(self.parent[:])res=INFs,g=None,Nonefor i in range(self.n):for j in self.edges[i]:if dist[j][i]+1<res:res=dist[j][i]+1s,g=i,jif res>=INF:return []else:self.parent=history[g]return self.path_restoring(g+self.decrement,s+self.decrement)def dfs(self, start=None, goal=-1, time=0, save=False):""":param start: スタート地点:param goal: ゴール地点:param save: True = 前回の探索結果を保持する:return: ゴール地点までの距離。存在しなければ -1。ループがある時は最短距離とは限らないため注意。"""if start is None: start=self.decrementstart,goal=start-self.decrement,goal-self.decrementif not save:self.parent = [-1] * self.nif self.destroy:edges2 = self.edgeselse:edges2 = [self.edges[p].copy() for p in range(self.n)]parent,directed=self.parent,self.directedp, t = start, timeparent[p] = -2if p==goal:return twhile True:if edges2[p]:q = edges2[p].pop()if q == parent[p] and not directed:""" 逆流した時の処理 """continueif parent[q] != -1:""" サイクルで同一点を訪れた時の処理 """continueif q == goal:""" ゴール時の処理"""parent[q]=preturn t + 1""" p から q への引継ぎ"""parent[q] = pp, t = q, t + 1else:""" p から進める点がもう無い時の点 p における処理 """if p == start and t == time:breakp, t = parent[p], t-1""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """return -1def cycle_detector(self, start=None, time=0, save=False):""":param p: スタート地点:param save: True = 前回の探索結果を保持する(遅い):return: サイクルリストを返す。存在しない場合は []"""if start is None: start=self.decrementstart=start-self.decrementif not save:self.parent = [-1] * self.nself.finished=[0]*self.nif self.destroy:edges2 = self.edgeselse:edges2 = [self.edges[p].copy() for p in range(self.n)]p, t = start, timeself.parent[p] = -2history = [p+self.decrement]cycle = []while True:if edges2[p]:q = edges2[p].pop()if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """""""""""""""""""""""continueif self.parent[q] != -1:""" サイクルで同一点を訪れた時の処理 """if not self.finished[q] and not cycle:cycle_start=history.index(q+self.decrement)if save==False:return history[cycle_start:]else:cycle = history[cycle_start:]""""""""""""""""""""continue""" p から q への引継ぎ"""""""""""""""""""""""history.append(q+self.decrement)self.parent[q] = pp, t = q, t + 1else:""" p から進める点がもう無い時の点 p における処理 """self.finished[p]=1history.pop()""""""""""""""""""""if p == start and t == time:breakp, t = self.parent[p], t-1""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """""""""""""""""""""""return cycledef tree_counter(self, detail=False):""":param detail: True = サイクルのリストを返す:return: 木(閉路を含まない)の個数を返す"""self.destroy=True # これをしないと計算量が壊れるself.parent = [-1] * self.nself.finished=[0]*self.nconnection_number = 0cycle_list = []for p in range(self.n):if self.parent[p] == -1:connection_number += 1cycle = self.cycle_detector(p + self.decrement, save=True)if cycle:cycle_list.append(cycle)if not detail:return connection_number - len(cycle_list)else:return cycle_listdef path_detector(self, start=None, time=0, save=False):""":param p: スタート地点:param save: True = 前回の探索結果を保持する:return: 各点までの距離と何番目に発見したかを返す"""if start is None: start=self.decrementstart=start-self.decrementif not save:self.parent = [-1] * self.nedges2= []for i in range(self.n):edges2.append(sorted(self.edges[i], reverse=True))p, t = start, timeself.parent[p] = -2full_path = [(p + self.decrement,t)]while True:if edges2[p]:q = edges2[p].pop()if q == self.parent[p] and not self.directed:""" 逆流した時の処理 """""""""""""""""""""""continueif self.parent[q] != -1:""" サイクルで同一点を訪れた時の処理 """""""""""""""""""""""continue""" p から q への引継ぎ"""""""""""""""""""""""self.parent[q] = pp, t = q, t + 1full_path.append((p + self.decrement, t))else:""" p から進める点がもう無い時の点 p における処理 """""""""""""""""""""""if p == start and t == time:breakp, t = self.parent[p], t-1""" 点 p から親ノードに戻ってきた時の親ノードにおける処理 """full_path.append((p + self.decrement, t))""""""""""""""""""""return full_pathdef path_restoring(self,start,goal):start,goal=start-self.decrement,goal-self.decrementq=goalres=[]while q!=start:res.append(q+self.decrement)q=self.parent[q]if q<0: return -1res.append(start+self.decrement)return res[::-1]def draw(self):""":return: グラフを可視化"""import matplotlib.pyplot as pltimport networkx as nxif self.directed:G = nx.DiGraph()else:G = nx.Graph()for x in range(self.n):for y in self.edges[x]:G.add_edge(x + self.decrement, y + self.decrement)pos = nx.spring_layout(G)nx.draw_networkx(G, pos, connectionstyle='arc3, rad = 0.1')plt.axis("off")plt.show()##################################################################################################def make_graph(N_min=2, N_max=5, M_min=1, M_max=10, directed=False,decrement=True):"""自己ループの無いグラフを生成。N>=2:param directed: True = 有効グラフ:param decrement: True = 1-indexed:return:"""import randominput_data = []global inputN=random.randint(N_min,N_max,)if N>2:M_max2=(3*N-6)*(1+directed)else:M_max2=1M=random.randint(max(1,M_min),min(M_max,M_max2))print("#########")edges=set()for _ in range(1,M+1):edge=random.sample(range(decrement,N+decrement),2)if directed==False:edge.sort()edge=tuple(edge)if edge not in edges:edges.add(edge)print(N,len(edges))input_data.append(" ".join(map(str,(N,len(edges)))))for edge in edges:print(*edge)input_data.append(" ".join(map(str,edge)))print("#########")input_data=iter(input_data)input = lambda: next(input_data)def draw(N,edges,decrement=1):import matplotlib.pyplot as pltimport networkx as nxG=nx.Graph()for x in range(N):for y in edges[x]:G.add_edge(x+decrement,y+decrement)pos=nx.spring_layout(G)nx.draw_networkx(G,pos)plt.axis("off")plt.show()class UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):""" 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)"""tmp = []parents = self.parentswhile parents[x] >= 0:tmp.append(x)x = parents[x]for y in tmp:parents[y] = xreturn xdef union(self, x, y):""" 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。"""x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):""" xとyが同じ根の子かを判定 """return self.find(x) == self.find(y)def size(self, x):""" xの根のparent(= 要素数)を返す """return -self.parents[self.find(x)]def members(self, x):""" xが属するグループの要素をリストとして返す O(N)"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):""" 全ての根の要素をリストとして返す O(N)"""return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):""" グループの数を返す O(N)"""return len(self.roots())def size_list(self):""" 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""return [-x for x in self.parents if x < 0]def all_group_members(self):""" {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)"""res = [[] for _ in range(self.n)]for i in range(self.n):x = self.find(i)res[x].append(i)return {r: res[r] for r in self.roots()}def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())######################################################################def example_tree(N=10,show=True,decrement=1):global input# decrement=True: create 1-indexed treedef find(x):tmp=[]while parents[x]>=0:tmp.append(x)x=parents[x]for y in tmp: parents[y]=xreturn xdef union(x,y):x,y=find(x),find(y)if x==y: returnif parents[x]>parents[y]: x,y=y,xparents[x]+=parents[y]parents[y]=xdef same(x,y):return find(x)==find(y)import random# N = random.randint(2, N)parents=[-1]*Nedges=[]input_data=[]input_data.append(str(N))for i in range(N-1):while True:j=random.randint(0,N-1)if same(i,j): continueunion(i,j)edges.append((i+decrement,j+decrement))breakfor i,j in edges:input_data.append(" ".join(map(str,(i,j))))input_data=iter(input_data)input=lambda:next(input_data)if show:print("#######################")print(N)for p in edges:print(*p)print("#######################")return edgesdef example_special_tree(N, type, show=True, decrement=1):global inputedges = []if type=="path":for i in range(N-1):edges.append((i+decrement,i+1+decrement))if type=="star":for i in range(N-1):edges.append((i,i+1+decrement))if type=="binary":i = 1while True:if (i<<1) >= N: breakedges.append((i-1+decrement, (i<<1)-1+decrement))if (i<<1)+1 >= N: breakedges.append((i-1+decrement, (i<<1)+decrement))i += 1input_data=[]input_data.append(str(N))for i,j in edges:input_data.append(" ".join(map(str,(i,j))))input_data=iter(input_data)input=lambda:next(input_data)if show:print("#######################")print(N)for p in edges:print(*p)print("#######################")return edgesdef example():global inputexample=iter("""6 91 22 33 44 55 65 15 26 16 2""".strip().split("\n"))input=lambda:next(example)######################################################################import sysinput=sys.stdin.readlinefrom collections import deque# example()# make_graph(N_min=7,N_max=7,M_min=10,M_max=10,directed=True)N, M = map(int, input().split())G = Graph(N, directed=False, decrement=True, destroy=False)U = UnionFind(N)for _ in range(M):x, y = map(int, input().split())G.add_edge(x, y)U.union(x-1, y-1)Q=int(input())for _ in range(Q):a=int(input())p, dist = G.most_distant_point(start=a)if dist==0:print(0,0)else:k=(dist-1).bit_length()print(U.size(a-1)-1, k)