結果

問題 No.812 Change of Class
ユーザー NoneNone
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Graph:
def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
self.n = n
self.directed = directed
self.decrement = decrement
self.destroy = destroy
self.edges = [set() for _ in range(self.n)]
self.parent = [-1]*self.n
for x, y in edges:
self.add_edge(x,y)
def add_edge(self, x, y):
if self.decrement:
x -= 1
y -= 1
self.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.decrement
start,goal=start-self.decrement,goal-self.decrement
if not save:
self.parent = [-1] * self.n
p, t = start, time
self.parent[p] = -2
next_set = deque([(p, t)])
if p==goal:
return t
while next_set:
p, t = next_set.popleft()
for q in self.edges[p]:
if q == self.parent[p] and not self.directed:
""" """
continue
if self.parent[q] != -1:
""" """
continue
if q == goal:
self.parent[q]=p
return t + 1
self.parent[q] = p
next_set.append((q, t + 1))
return -1
def connection_counter(self):
"""
:return:
"""
cnt = 0
self.parent = [-1] * self.n
for start in range(self.n):
if self.parent[start] == -1:
cnt += 1
self.bfs(start + self.decrement, save=True)
return cnt
def connection_detail(self):
"""
:return: (, )
: M=N-1
"""
ver_edge=[]
self.parent = [-1] * self.n
for 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_edge
def _detail(self, start=None):
"""
:param start:
:param save: True =
"""
if start is None: start=self.decrement
start=start-self.decrement
p, t = start, 0
self.parent[p] = -2
next_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:
""" """
continue
sub_edges.add((min(p,q),max(p,q)))
if self.parent[q] != -1:
""" """
continue
self.parent[q] = p
next_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.n
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
p, t = start, 0
self.parent[p] = -2
dist[p] = 0
next_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:
""" """
continue
if self.parent[q] != -1:
""" """
continue
dist[q] = t + 1
self.parent[q] = p
next_set.append((q, t + 1))
return dist
def parent_list(self, start=None):
"""
:return:
-1
"""
if start is None: start=self.decrement
self.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.n
if start is None: start=self.decrement
start=start-self.decrement
res = (start, 0)
temp = 0
for i, dist in enumerate(self.distance_list(start+self.decrement, save=save)):
if dist > temp:
temp = dist
res = (i + self.decrement, dist)
return res
def diameter(self, save=False):
"""
O(N)
:return: ()
"""
if not save:
self.parent = [-1] * self.n
p = 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=0
self.parent = [-1] * self.n
p, t = start, 0
self.parent[p] = -2
next_set=deque()
starts=set()
for q in self.edges[p]:
next_set.append((q, t))
self.parent[q]=p
starts.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:
""" """
continue
if self.parent[q] != -1:
""" """
if q in starts:
cycle=[q+self.decrement]
r=p
while r not in starts:
cycle.append(r+self.decrement)
r=self.parent[r]
if r<0: return -1
cycle.append(r+self.decrement)
cycle.append(start+self.decrement)
res.append(cycle[::-1])
flg=1
break
continue
self.parent[q] = p
next_set.append((q, t + 1))
return res
def minimum_cycle_directed(self):
"""
O(V(V+E))
"""
INF=10**18
dist=[]
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=INF
s,g=None,None
for i in range(self.n):
for j in self.edges[i]:
if dist[j][i]+1<res:
res=dist[j][i]+1
s,g=i,j
if 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.decrement
start,goal=start-self.decrement,goal-self.decrement
if not save:
self.parent = [-1] * self.n
if self.destroy:
edges2 = self.edges
else:
edges2 = [self.edges[p].copy() for p in range(self.n)]
parent,directed=self.parent,self.directed
p, t = start, time
parent[p] = -2
if p==goal:
return t
while True:
if edges2[p]:
q = edges2[p].pop()
if q == parent[p] and not directed:
""" """
continue
if parent[q] != -1:
""" """
continue
if q == goal:
""" """
parent[q]=p
return t + 1
""" p q """
parent[q] = p
p, t = q, t + 1
else:
""" p p """
if p == start and t == time:
break
p, t = parent[p], t-1
""" p """
return -1
def cycle_detector(self, start=None, time=0, save=False):
"""
:param p:
:param save: True = ()
:return: []
"""
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
self.finished=[0]*self.n
if self.destroy:
edges2 = self.edges
else:
edges2 = [self.edges[p].copy() for p in range(self.n)]
p, t = start, time
self.parent[p] = -2
history = [p+self.decrement]
cycle = []
while True:
if edges2[p]:
q = edges2[p].pop()
if q == self.parent[p] and not self.directed:
""" """
""""""""""""""""""""
continue
if 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] = p
p, t = q, t + 1
else:
""" p p """
self.finished[p]=1
history.pop()
""""""""""""""""""""
if p == start and t == time:
break
p, t = self.parent[p], t-1
""" p """
""""""""""""""""""""
return cycle
def tree_counter(self, detail=False):
"""
:param detail: True =
:return: ()
"""
self.destroy=True #
self.parent = [-1] * self.n
self.finished=[0]*self.n
connection_number = 0
cycle_list = []
for p in range(self.n):
if self.parent[p] == -1:
connection_number += 1
cycle = 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_list
def path_detector(self, start=None, time=0, save=False):
"""
:param p:
:param save: True =
:return:
"""
if start is None: start=self.decrement
start=start-self.decrement
if not save:
self.parent = [-1] * self.n
edges2= []
for i in range(self.n):
edges2.append(sorted(self.edges[i], reverse=True))
p, t = start, time
self.parent[p] = -2
full_path = [(p + self.decrement,t)]
while True:
if edges2[p]:
q = edges2[p].pop()
if q == self.parent[p] and not self.directed:
""" """
""""""""""""""""""""
continue
if self.parent[q] != -1:
""" """
""""""""""""""""""""
continue
""" p q """
""""""""""""""""""""
self.parent[q] = p
p, t = q, t + 1
full_path.append((p + self.decrement, t))
else:
""" p p """
""""""""""""""""""""
if p == start and t == time:
break
p, t = self.parent[p], t-1
""" p """
full_path.append((p + self.decrement, t))
""""""""""""""""""""
return full_path
def path_restoring(self,start,goal):
start,goal=start-self.decrement,goal-self.decrement
q=goal
res=[]
while q!=start:
res.append(q+self.decrement)
q=self.parent[q]
if q<0: return -1
res.append(start+self.decrement)
return res[::-1]
def draw(self):
"""
:return:
"""
import matplotlib.pyplot as plt
import networkx as nx
if 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 random
input_data = []
global input
N=random.randint(N_min,N_max,)
if N>2:
M_max2=(3*N-6)*(1+directed)
else:
M_max2=1
M=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 plt
import networkx as nx
G=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 = n
self.parents = [-1] * n
def find(self, x):
""" (x)"""
tmp = []
parents = self.parents
while parents[x] >= 0:
tmp.append(x)
x = parents[x]
for y in tmp:
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 same(self, x, y):
""" xy """
return self.find(x) == self.find(y)
def size(self, x):
""" xparent(= ) """
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 tree
def find(x):
tmp=[]
while parents[x]>=0:
tmp.append(x)
x=parents[x]
for y in tmp: parents[y]=x
return x
def union(x,y):
x,y=find(x),find(y)
if x==y: return
if parents[x]>parents[y]: x,y=y,x
parents[x]+=parents[y]
parents[y]=x
def same(x,y):
return find(x)==find(y)
import random
# N = random.randint(2, N)
parents=[-1]*N
edges=[]
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): continue
union(i,j)
edges.append((i+decrement,j+decrement))
break
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 edges
def example_special_tree(N, type, show=True, decrement=1):
global input
edges = []
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 = 1
while True:
if (i<<1) >= N: break
edges.append((i-1+decrement, (i<<1)-1+decrement))
if (i<<1)+1 >= N: break
edges.append((i-1+decrement, (i<<1)+decrement))
i += 1
input_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 edges
def example():
global input
example=iter(
"""
6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2
"""
.strip().split("\n"))
input=lambda:next(example)
######################################################################
import sys
input=sys.stdin.readline
from 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0