結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2020-05-19 22:48:33 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,021 ms / 4,500 ms |
| コード長 | 8,127 bytes |
| コンパイル時間 | 175 ms |
| コンパイル使用メモリ | 82,152 KB |
| 実行使用メモリ | 197,996 KB |
| 最終ジャッジ日時 | 2024-10-01 23:10:54 |
| 合計ジャッジ時間 | 20,499 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
from heapq import heappop,heappush,heapify
from collections import deque
class Graph(): #non-directed
def __init__(self,n,edge):
self.n = n
self.graph = [[] for _ in range(n)]
self.deg = [0 for _ in range(n)]
for e in edge:
self.graph[e[0] - 1].append(e[1] - 1)
self.graph[e[1] - 1].append(e[0] - 1)
self.deg[e[0] - 1] += 1
self.deg[e[1] - 1] += 1
def lowlink(self): #DFS木, ord, lowを計算
self.ord = [None for _ in range(self.n)]
self.low = [None for _ in range(self.n)]
self.group = [None for _ in range(self.n)]
self.prev = [None for _ in range(self.n)]
self.tree = [[] for _ in range(self.n)]
self.sorted = []
order = 0
count = 0
low = [None for _ in range(self.n)]
for s in range(self.n):
if self.group[s] is None:
stack = [(s, None)]
while stack:
node, par = stack.pop()
if self.group[node] is None:
self.group[node] = count
self.ord[node] = order
self.sorted.append(node)
order += 1
if par is not None:
self.prev[node] = par
self.tree[par].append(node)
for adj in self.graph[node]:
if self.group[adj] is None:
stack.append((adj, node))
count += 1
for node in self.sorted[::-1]:
self.low[node] = self.ord[node]
for adj in self.graph[node]:
if self.prev[adj] == node:
self.low[node] = min(self.low[node], self.low[adj])
elif self.prev[node] == adj:
continue
else:
self.low[node] = min(self.low[node], self.ord[adj])
def articulation(self):
res = []
for node in range(self.n):
if self.prev[node] is None and len(self.tree[node]) > 1:
res.append(node)
if self.prev[node] is not None:
for adj in self.tree[node]:
if self.ord[node] <= self.low[adj]:
res.append(node)
break
return res
def bridge(self):
res = []
for node in range(self.n):
for adj in self.tree[node]:
if self.ord[node] < self.low[adj]:
res.append((node, adj))
return res
class Tree():
def __init__(self, n, edge):
self.n = n
self.tree = [[] for _ in range(n)]
for e in edge:
self.tree[e[0] - 1].append(e[1] - 1)
self.tree[e[1] - 1].append(e[0] - 1)
def setroot(self, root):
self.root = root
self.parent = [None for _ in range(self.n)]
self.parent[root] = -1
self.depth = [None for _ in range(self.n)]
self.depth[root] = 0
self.order = []
self.order.append(root)
self.size = [1 for _ in range(self.n)]
stack = [root]
while stack:
node = stack.pop()
for adj in self.tree[node]:
if self.parent[adj] is None:
self.parent[adj] = node
self.depth[adj] = self.depth[node] + 1
self.order.append(adj)
stack.append(adj)
for node in self.order[::-1]:
for adj in self.tree[node]:
if self.parent[node] == adj:
continue
self.size[node] += self.size[adj]
def heavylight_decomposition(self):
self.order = [None for _ in range(self.n)]
self.head = [None for _ in range(self.n)]
self.head[self.root] = self.root
self.next = [None for _ in range(self.n)]
stack = [self.root]
order = 0
while stack:
node = stack.pop()
self.order[node] = order
order += 1
maxsize = 0
for adj in self.tree[node]:
if self.parent[node] == adj:
continue
if maxsize < self.size[adj]:
maxsize = self.size[adj]
self.next[node] = adj
for adj in self.tree[node]:
if self.parent[node] == adj or self.next[node] == adj:
continue
self.head[adj] = adj
stack.append(adj)
if self.next[node] is not None:
self.head[self.next[node]] = self.head[node]
stack.append(self.next[node])
def range_hld(self, u, v, edge=False):
res = []
while True:
if self.order[u] > self.order[v]: u, v = v, u
if self.head[u] != self.head[v]:
res.append((self.order[self.head[v]], self.order[v] + 1))
v = self.parent[self.head[v]]
else:
res.append((self.order[u] + edge, self.order[v] + 1))
return res
def subtree_hld(self, u):
return self.order[u], self.order[u] + self.size[u]
def lca_hld(self, u, v):
while True:
if self.order[u] > self.order[v]: u, v = v, u
if self.head[u] != self.head[v]:
v = self.parent[self.head[v]]
else:
return u
class SegmentTree():
def __init__(self, arr, func=min, ie=2**63):
self.h = (len(arr) - 1).bit_length()
self.n = 2**self.h
self.ie = ie
self.func = func
self.tree = [ie for _ in range(2 * self.n)]
for i in range(len(arr)):
self.tree[self.n + i] = arr[i]
for i in range(1, self.n)[::-1]:
self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])
def set(self, idx, x):
idx += self.n
self.tree[idx] = x
while idx:
idx >>= 1
self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])
def query(self, lt, rt):
lt += self.n
rt += self.n
vl = vr = self.ie
while rt - lt > 0:
if lt & 1:
vl = self.func(vl, self.tree[lt])
lt += 1
if rt & 1:
rt -= 1
vr = self.func(self.tree[rt], vr)
lt >>= 1
rt >>= 1
return self.func(vl, vr)
import sys
input = sys.stdin.readline
INF = 10**18
N, M, Q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
g = Graph(N, edge)
g.lowlink()
bridge = set(g.bridge())
edge_no_bridge = []
for e in edge:
if (e[0] - 1, e[1] - 1) in bridge or (e[1] - 1, e[0] - 1) in bridge:
continue
edge_no_bridge.append(e)
graph_no_edge = Graph(N, edge_no_bridge)
graph_no_edge.lowlink()
decomposed = graph_no_edge.group
count = max(decomposed) + 1
decomposed_to_node = [[] for _ in range(count)]
for i in range(count):
decomposed_to_node[decomposed[i]].append(i)
branch = []
for a, b in bridge:
branch.append((decomposed[a] + 1, decomposed[b] + 1))
t = Tree(count, branch)
t.setroot(0)
t.heavylight_decomposition()
arr = [(-1, None) for _ in range(count)]
st = SegmentTree(arr, max, (-1, None))
enemy = [[] for _ in range(count)]
res = []
for _ in range(Q):
q, x, y = map(int, input().split())
if q == 1:
heappush(enemy[decomposed[x - 1]], -y)
st.set(t.order[decomposed[x - 1]], (-enemy[decomposed[x - 1]][0], decomposed[x - 1]))
else:
tmp = (-1, None)
for lt, rt in t.range_hld(decomposed[x - 1], decomposed[y - 1]):
tmp = max(tmp, st.query(lt, rt))
value, idx = tmp
res.append(value)
if value != -1:
if enemy[idx]:
heappop(enemy[idx])
if enemy[idx]:
st.set(t.order[idx], (-enemy[idx][0], idx))
else:
st.set(t.order[idx], (-1, None))
print('\n'.join(map(str, res)))