結果
問題 | No.2439 Fragile Apple Tree |
ユーザー | 👑 tatyam |
提出日時 | 2023-08-18 18:55:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,552 ms / 10,000 ms |
コード長 | 3,196 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 87,228 KB |
実行使用メモリ | 450,064 KB |
最終ジャッジ日時 | 2023-08-19 00:20:32 |
合計ジャッジ時間 | 73,605 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,240 ms
175,204 KB |
testcase_01 | AC | 4,514 ms
207,296 KB |
testcase_02 | AC | 4,519 ms
205,804 KB |
testcase_03 | AC | 2,006 ms
448,364 KB |
testcase_04 | AC | 2,807 ms
450,064 KB |
testcase_05 | AC | 4,552 ms
205,900 KB |
testcase_06 | AC | 4,056 ms
193,012 KB |
testcase_07 | AC | 3,960 ms
184,884 KB |
testcase_08 | AC | 4,176 ms
185,236 KB |
testcase_09 | AC | 77 ms
87,264 KB |
testcase_10 | AC | 78 ms
87,248 KB |
testcase_11 | AC | 77 ms
87,308 KB |
testcase_12 | AC | 78 ms
86,792 KB |
testcase_13 | AC | 80 ms
87,220 KB |
testcase_14 | AC | 4,317 ms
182,048 KB |
testcase_15 | AC | 2,810 ms
185,448 KB |
testcase_16 | AC | 3,624 ms
185,404 KB |
testcase_17 | AC | 3,572 ms
191,488 KB |
testcase_18 | AC | 2,443 ms
181,876 KB |
testcase_19 | AC | 1,661 ms
137,964 KB |
testcase_20 | AC | 929 ms
127,560 KB |
testcase_21 | AC | 528 ms
100,564 KB |
testcase_22 | AC | 2,393 ms
153,688 KB |
testcase_23 | AC | 1,240 ms
123,008 KB |
testcase_24 | AC | 1,395 ms
133,264 KB |
testcase_25 | AC | 1,591 ms
163,168 KB |
testcase_26 | AC | 2,132 ms
171,820 KB |
testcase_27 | AC | 1,787 ms
150,612 KB |
testcase_28 | AC | 80 ms
87,328 KB |
testcase_29 | AC | 79 ms
87,232 KB |
testcase_30 | AC | 83 ms
90,696 KB |
testcase_31 | AC | 1,442 ms
196,888 KB |
testcase_32 | AC | 1,448 ms
197,232 KB |
ソースコード
# パス減算 → 破壊チェック → 破壊された辺に掛かっていた重みを上にパス加算 # 必要な操作: 辺属性, パス加算, 区間 min の max-right, 1 辺取得 import sys sys.setrecursionlimit(2 ** 20) input = sys.stdin.readline INF = 1 << 61 SIZ = 1 << 19 LOG = 19 d = [INF] * (SIZ * 2) lz = [0] * (SIZ * 2) def all_apply(k: int, f: int): d[k] += f lz[k] += f def push(k: int): if lz[k]: all_apply(2 * k, lz[k]) all_apply(2 * k + 1, lz[k]) lz[k] = 0 def update(k: int): d[k] = min(d[k << 1], d[k << 1 | 1]) def get(p: int): p += SIZ for i in range(LOG, 0, -1): push(p >> i) return d[p] def add(l: int, r: int, x: int): if l == r: return l += SIZ r += SIZ for i in range(LOG, 0, -1): if l >> i << i != l: push(l >> i) if r >> i << i != r: push((r - 1) >> i) def F(l: int, r: int): while l < r: if l & 1: all_apply(l, x) l += 1 if r & 1: r -= 1 all_apply(r, x) l >>= 1 r >>= 1 F(l, r) for i in range(1, LOG + 1): if l >> i << i != l: update(l >> i) if r >> i << i != r: update((r - 1) >> i) def broken_edge() -> int: r = 2 for _ in range(LOG): push(r - 1) r <<= 1 if d[r - 1] > 0: r -= 1 return r - SIZ - 1 N, Q = map(int, input().split()) edge: list[list[int]] = [list(map(int, input().split())) for _ in range(N - 1)] g: list[list[int]] = [[] for _ in range(N)] for e in edge: e[0] -= 1 e[1] -= 1 a, b, c = e g[a].append(b) g[b].append(a) siz = [1] * N parent = [-1] * N C = [0] * N q = [0] for i in q: for j in g[i]: parent[j] = i q.append(j) g[j].remove(i) for i in reversed(q): p = parent[i] if p != -1: siz[p] += siz[i] if g[i]: j = max(g[i], key=lambda x: siz[x]) g[i].remove(j) g[i].insert(0, j) C[0] = INF for a, b, c in edge: a = min(a, b, key=lambda x: siz[x]) C[a] = c heavy = [0] * N index = [0] * N idx = 0 def dfs(i: int): global idx index[i] = idx add(idx, idx + 1, C[i] - INF) idx += 1 if not g[i]: return heavy[g[i][0]] = heavy[i] dfs(g[i][0]) for j in g[i][1:]: heavy[j] = j dfs(j) dfs(0) rev = [-1] * N for i in range(N): rev[index[i]] = i vertices = N erased = [False] * N def path_add(i: int, x: int): while i > 0: h = heavy[i] add(index[h], index[i] + 1, x) i = parent[h] def dfs(i: int): global vertices if erased[i]: return erased[i] = True vertices -= 1 x = C[i] - get(index[i]) add(index[i], index[i] + 1, INF) for j in g[i]: dfs(j) for _ in range(Q): query = input() if query[0] == '1': v, x = map(int, query[2:].split()) v -= 1 # 0 - v パスに x を減算 path_add(v, -x) # <= 0 の辺を切る while d[1] <= 0: i = rev[broken_edge()] path_add(i, C[i] - get(index[i])) dfs(i) else: print(vertices)