結果
問題 | No.1030 だんしんぐぱーりない |
ユーザー | maspy |
提出日時 | 2020-04-18 01:07:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 619 ms / 2,000 ms |
コード長 | 3,040 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,012 KB |
実行使用メモリ | 130,912 KB |
最終ジャッジ日時 | 2024-04-14 18:34:16 |
合計ジャッジ時間 | 19,824 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
52,608 KB |
testcase_01 | AC | 37 ms
52,608 KB |
testcase_02 | AC | 37 ms
52,736 KB |
testcase_03 | AC | 36 ms
52,736 KB |
testcase_04 | AC | 37 ms
53,248 KB |
testcase_05 | AC | 518 ms
124,712 KB |
testcase_06 | AC | 446 ms
115,560 KB |
testcase_07 | AC | 400 ms
98,332 KB |
testcase_08 | AC | 387 ms
102,588 KB |
testcase_09 | AC | 470 ms
123,612 KB |
testcase_10 | AC | 342 ms
87,084 KB |
testcase_11 | AC | 480 ms
107,760 KB |
testcase_12 | AC | 507 ms
119,944 KB |
testcase_13 | AC | 457 ms
115,388 KB |
testcase_14 | AC | 532 ms
117,916 KB |
testcase_15 | AC | 378 ms
92,680 KB |
testcase_16 | AC | 500 ms
112,936 KB |
testcase_17 | AC | 482 ms
123,804 KB |
testcase_18 | AC | 551 ms
120,836 KB |
testcase_19 | AC | 418 ms
97,732 KB |
testcase_20 | AC | 436 ms
108,280 KB |
testcase_21 | AC | 421 ms
112,432 KB |
testcase_22 | AC | 431 ms
103,504 KB |
testcase_23 | AC | 472 ms
104,920 KB |
testcase_24 | AC | 429 ms
97,188 KB |
testcase_25 | AC | 436 ms
105,744 KB |
testcase_26 | AC | 408 ms
88,516 KB |
testcase_27 | AC | 405 ms
92,132 KB |
testcase_28 | AC | 512 ms
114,924 KB |
testcase_29 | AC | 440 ms
116,356 KB |
testcase_30 | AC | 422 ms
103,272 KB |
testcase_31 | AC | 431 ms
106,152 KB |
testcase_32 | AC | 484 ms
116,464 KB |
testcase_33 | AC | 495 ms
121,264 KB |
testcase_34 | AC | 351 ms
87,576 KB |
testcase_35 | AC | 613 ms
130,912 KB |
testcase_36 | AC | 619 ms
119,324 KB |
testcase_37 | AC | 604 ms
129,296 KB |
testcase_38 | AC | 604 ms
119,496 KB |
testcase_39 | AC | 603 ms
119,192 KB |
testcase_40 | AC | 38 ms
53,248 KB |
testcase_41 | AC | 37 ms
52,992 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines class SegTree: """ segment tree with point modification and range product access. """ data_unit = 1 << 30 data_f = min def __init__(self, N): self.N = N self.data = [self.data_unit] * (N + N) def build(self, raw_data): data = self.data f = self.data_f N = self.N data[N:] = raw_data[:] for i in range(N - 1, 0, -1): data[i] = f(data[i << 1], data[i << 1 | 1]) def set_val(self, i, x): data = self.data f = self.data_f i += self.N data[i] = x while i > 1: i >>= 1 data[i] = f(data[i << 1], data[i << 1 | 1]) def fold(self, L, R): """ compute for [L, R) """ vL = vR = self.data_unit data = self.data f = self.data_f L += self.N R += self.N while L < R: if L & 1: vL = f(vL, data[L]) L += 1 if R & 1: R -= 1 vR = f(data[R], vR) L >>= 1 R >>= 1 return f(vL, vR) def create_euler_tour(graph, root=1): """1-indexed graph""" V = len(graph) par = [0] * V depth = [0] * V depth[root] = 0 tour = [root] st = [root] while st: x = st[-1] if not graph[x]: st.pop() tour.append(par[x]) continue y = graph[x].pop() if y == par[x]: continue par[y] = x depth[y] = depth[x] + 1 st.append(y) tour.append(y) return tour, depth, par N, K, Q = map(int, readline().split()) C = tuple(map(int, readline().split())) A = list(map(int, readline().split())) graph = [[] for _ in range(N + 1)] lines = readlines() for line in lines[: N - 1]: e, f = map(int, line.split()) graph[f].append(e) tour, depth, parent = create_euler_tour(graph) ind = [0] * (N + 1) for i, x in enumerate(tour): ind[x] = i tour_dep = [depth[v] for v in tour] seg_min = SegTree(K) seg_max = SegTree(K) seg_max.data_f = max seg_max.data_unit = 0 seg_lca = SegTree(N + N - 1) seg_lca.data_unit = None def f(x, y): if x is None: return y if y is None: return x if depth[x] < depth[y]: return x else: return y seg_lca.data_f = f seg_lca.build(tour) def lca(x, y): return seg_lca.fold(x, y + 1) seg_min.build([ind[x] for x in A]) seg_max.build([ind[x] for x in A]) LCA = [] for query in lines[N - 1:]: t, x, y = map(int, query.split()) if t == 2: L = seg_min.fold(x - 1, y) R = seg_max.fold(x - 1, y) v = lca(L, R) LCA.append(v) else: x -= 1 i = A[x] A[x] = y seg_min.set_val(x, ind[y]) seg_max.set_val(x, ind[y]) cost = [0] * (N + 1) for v in tour: cost[v] = max(C[v - 1], cost[parent[v]]) for v in LCA: print(cost[v])