結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2020-05-19 22:42:21 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,072 bytes |
| コンパイル時間 | 185 ms |
| コンパイル使用メモリ | 82,532 KB |
| 実行使用メモリ | 202,640 KB |
| 最終ジャッジ日時 | 2024-04-09 22:35:06 |
| 合計ジャッジ時間 | 18,376 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 42 ms
56,568 KB |
| testcase_01 | AC | 42 ms
56,632 KB |
| testcase_02 | AC | 41 ms
56,776 KB |
| testcase_03 | AC | 42 ms
56,852 KB |
| testcase_04 | AC | 171 ms
80,444 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | AC | 1,095 ms
167,028 KB |
| testcase_13 | AC | 856 ms
197,280 KB |
| testcase_14 | AC | 881 ms
177,000 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | AC | 1,366 ms
201,876 KB |
| testcase_19 | AC | 1,450 ms
202,344 KB |
ソースコード
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, i) for i in t.order]
st = SegmentTree(arr, max, (-INF, -INF))
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, -INF)
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 enemy[idx]:
heappop(enemy[idx])
if enemy[idx]:
st.set(t.order[idx], (-enemy[idx][0], idx))
else:
st.set(t.order[idx], (-1, idx))
print('\n'.join(map(str, res)))