結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 prin_kemkem
|
| 提出日時 | 2023-03-24 11:02:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,252 ms / 4,500 ms |
| コード長 | 15,588 bytes |
| コンパイル時間 | 665 ms |
| コンパイル使用メモリ | 82,500 KB |
| 実行使用メモリ | 168,232 KB |
| 最終ジャッジ日時 | 2024-09-18 16:00:10 |
| 合計ジャッジ時間 | 20,402 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
from collections import defaultdict, deque, Counter
import copy
from itertools import combinations, permutations, product, accumulate
from heapq import heapify, heappop, heappush
import math
import bisect
import sys
# sys.setrecursionlimit(700000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)
#################################################
class LowLink():
def __init__(self, adj):
self.n = len(adj)
self.ord = [None]*self.n
self.low = [None]*self.n
self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
self.tps = [] # 頂点のトポロジカルソート
# DFSでord, son, parent, tpsを求め、lowを初期化
t = 0 # 今までに訪れた頂点数
stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
while stack:
pre, now = stack.pop()
if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
self.back_edge[pre].append(now)
continue
if pre is not None:
self.son[pre].append(now)
self.tps.append(now)
self.ord[now] = t # 行きがけ順を書き込む
self.low[now] = self.ord[now] # low[now]をord[now]で初期化
t += 1
for next in adj[now]:
if next == pre: continue
stack.append((now, next))
# ボトムアップ順にchminしてlowを求める
for u in reversed(self.tps[1:]):
for v in self.son[u]:
self.low[u] = min(self.low[u], self.low[v])
# 二重辺連結成分分解
def two_edge_connected_component(self):
tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
idx = 0 # 今いる頂点の連結成分の番号
while sub_roots:
stack = [sub_roots.pop()] # 部分木の根からDFS
tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
while stack:
pre, now = stack.pop()
tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
tecc_tree[tecc_idx[pre]].append(idx)
for next in self.son[now]:
if self.low[next] > self.ord[now]: # 橋なら
sub_roots.append((now, next)) # その先は別の連結成分
else: # そうでないなら
stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
idx += 1
return tecc, tecc_idx, tecc_tree
# 二重頂点連結成分分解
def biconnected_component(self):
bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
idx = 0 # 今いる頂点の連結成分の番号
while sub_roots:
stack = [sub_roots.pop()] # 部分木の根からDFS
bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
while stack:
pre, now = stack.pop()
if pre is not None: # 直前に通った辺が存在するなら
bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加
bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
if now == 0: # 今いる頂点nowが根で
if len(self.son[now]) >= 2: # 関節点であるなら
for next in self.son[now]:
is_ap[now] = True # 関節点であことを記録
sub_roots.append((now, next)) # その先は別の連結成分
bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
bcv.pop()
idx -= 1
else: # 関節点でないなら
for next in self.son[now]:
stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
else: # 根でなく
for next in self.son[now]:
if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
is_ap[now] = True # 関節点であることを記録
sub_roots.append((now, next)) # その先は別の連結成分
else: # 関節点でないなら
stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
if now == 0 and len(self.son[now]) <= 1:
for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
bce[idx].append((now, back)) # 連結成分idxに追加
idx += 1
return bce, bcv, is_ap
# block-cut treeを構築
def block_cut_tree(self):
bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
num_ap = sum(is_ap) # 関節点の個数
bc = [[] for _ in range(num_ap+len(bcv))]
# bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
# [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
# [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
# block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
bc_idx = [None]*self.n
# bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
# 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
idx = 0 # 今見ているblock-cut tree上の頂点番号
for v in range(self.n): # (元グラフの)各頂点vについて
if is_ap[v]: # 関節点なら
bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
bc_idx[v] = idx
idx += 1
for bcv_i in bcv: # 各連結成分の
for v in bcv_i: # 各頂点vについて
if is_ap[v]: # 関節点なら
bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
bc_tree[bc_idx[v]].append(idx)
else: # そうでないなら
bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
bc_idx[v] = idx
idx += 1
return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap
class HLD:
# https://github.com/shakayami/ACL-for-python/blob/master/segtree.py
class segtree():
n=1
size=1
log=2
d=[0]
op=None
e=10**15
def __init__(self,V,OP,E):
self.n=len(V)
self.op=OP
self.e=E
self.log=(self.n-1).bit_length()
self.size=1<<self.log
self.d=[E for i in range(2*self.size)]
for i in range(self.n):
self.d[self.size+i]=V[i]
for i in range(self.size-1,0,-1):
self.update(i)
def set(self,p,x):
assert 0<=p and p<self.n
p+=self.size
self.d[p]=x
for i in range(1,self.log+1):
self.update(p>>i)
def get(self,p):
assert 0<=p and p<self.n
return self.d[p+self.size]
def prod(self,l,r):
assert 0<=l and l<=r and r<=self.n
sml=self.e
smr=self.e
l+=self.size
r+=self.size
while(l<r):
if (l&1):
sml=self.op(sml,self.d[l])
l+=1
if (r&1):
smr=self.op(self.d[r-1],smr)
r-=1
l>>=1
r>>=1
return self.op(sml,smr)
def all_prod(self):
return self.d[1]
def max_right(self,l,f):
assert 0<=l and l<=self.n
assert f(self.e)
if l==self.n:
return self.n
l+=self.size
sm=self.e
while(1):
while(l%2==0):
l>>=1
if not(f(self.op(sm,self.d[l]))):
while(l<self.size):
l=2*l
if f(self.op(sm,self.d[l])):
sm=self.op(sm,self.d[l])
l+=1
return l-self.size
sm=self.op(sm,self.d[l])
l+=1
if (l&-l)==l:
break
return self.n
def min_left(self,r,f):
assert 0<=r and r<=self.n
assert f(self.e)
if r==0:
return 0
r+=self.size
sm=self.e
while(1):
r-=1
while(r>1 and (r%2)):
r>>=1
if not(f(self.op(self.d[r],sm))):
while(r<self.size):
r=(2*r+1)
if f(self.op(self.d[r],sm)):
sm=self.op(self.d[r],sm)
r-=1
return r+1-self.size
sm=self.op(self.d[r],sm)
if (r& -r)==r:
break
return 0
def update(self,k):
self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
def __str__(self):
return str([self.get(i) for i in range(self.n)])
def __init__(self, adj, weights, op, e, root=0) -> None:
self.n = len(adj)
self.root = root
self.parent = [None]*self.n
stack = [root]
tps = []
while stack:
u = stack.pop()
tps.append(u)
for v in adj[u]:
adj[v].remove(u)
self.parent[v] = u
stack.append(v)
size = [1]*self.n
heavy = [None]*self.n
for u in reversed(tps):
ms = -inf
for v in adj[u]:
if size[v] > ms:
heavy[u] = v
ms = size[v]
size[u] += size[v]
del tps, size
self.idx = [None]*self.n
self.heavy_root = [None]*self.n
stack = [(None, root)]
i = 0
while stack:
p, u = stack.pop()
self.idx[u] = i
if p is not None:
self.parent[i] = self.idx[p]
if self.heavy_root[i] is None:
self.heavy_root[i] = i
for v in adj[u]:
if v == heavy[u]: continue
stack.append((u, v))
if heavy[u] is not None:
self.heavy_root[i+1] = self.heavy_root[i]
stack.append((u, heavy[u]))
i += 1
array = [None]*self.n
self.vertex = [None]*self.n
for u, w in enumerate(weights):
array[self.idx[u]] = w
self.vertex[self.idx[u]] = u
self.paths = self.segtree(array, op, e)
def prod(self, u, v):
u, v = self.idx[u], self.idx[v]
ret = self.paths.e
while self.heavy_root[u] != self.heavy_root[v]:
if u > v:
ret = self.paths.op(ret, self.paths.prod(self.heavy_root[u], u+1))
u = self.parent[self.heavy_root[u]]
else:
ret = self.paths.op(ret, self.paths.prod(self.heavy_root[v], v+1))
v = self.parent[self.heavy_root[v]]
if u > v: u, v = v, u
return self.paths.op(ret, self.paths.prod(u, v+1))
def set(self, u, w):
self.paths.set(self.idx[u], w)
def lca(self, u, v):
u, v = self.idx[u], self.idx[v]
while self.heavy_root[u] != self.heavy_root[v]:
if u > v:
u = self.parent[self.heavy_root[u]]
else:
v = self.parent[self.heavy_root[v]]
return self.vertex[min(u, v)]
def through(self, u, v, x):
u, v, x = self.idx[u], self.idx[v], self.idx[x]
while self.heavy_root[u] != self.heavy_root[v]:
if u > v:
if self.heavy_root[u] <= x <= u: return True
u = self.parent[self.heavy_root[u]]
else:
if self.heavy_root[v] <= x <= v: return True
v = self.parent[self.heavy_root[v]]
if u > v: u, v = v, u
return u <= x <= v
N, M, Q = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1; b -= 1
adj[a].append(b)
adj[b].append(a)
ll = LowLink(adj)
tecc, tecc_idx, tecc_tree = ll.two_edge_connected_component()
hld = HLD(tecc_tree, [(-1, i) for i in range(len(tecc))], max, (-inf, -inf))
weights = [[] for _ in range(len(tecc))]
for _ in range(Q):
q, x, y = map(int, input().split())
if q == 1:
u, w = tecc_idx[x-1], y
heappush(weights[u], -w)
hld.set(u, (-weights[u][0], u))
else:
s, t = tecc_idx[x-1], tecc_idx[y-1]
ans, u = hld.prod(s, t)
print(ans)
if weights[u]:
heappop(weights[u])
hld.set(u, (-weights[u][0] if weights[u] else -1, u))