結果
問題 | No.2439 Fragile Apple Tree |
ユーザー |
![]() |
提出日時 | 2023-08-18 18:24:10 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,255 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 634,332 KB |
最終ジャッジ日時 | 2024-11-28 02:12:58 |
合計ジャッジ時間 | 220,904 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 TLE * 11 MLE * 3 |
ソースコード
# パス減算 → 破壊チェック → 破壊された辺に掛かっていた重みを上にパス加算# 必要な操作: 辺属性, パス加算, 区間 min の max-right, 1 辺取得import sysimport pypyjitpypyjit.set_param('max_unroll_recursion=0')sys.setrecursionlimit(2 ** 20)input = sys.stdin.readlineINF = 1 << 61SIZ = 1 << 19LOG = 19d = [INF] * (SIZ * 2)lz = [0] * (SIZ * 2)def all_apply(k: int, f: int):d[k] += flz[k] += fdef push(k: int):if lz[k]:all_apply(2 * k, lz[k])all_apply(2 * k + 1, lz[k])lz[k] = 0def update(k: int):d[k] = min(d[k << 1], d[k << 1 | 1])def get(p: int):p += SIZfor i in range(LOG, 0, -1): push(p >> i)return d[p]def add(l: int, r: int, x: int):if l == r: returnl += SIZr += SIZfor 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 += 1if r & 1:r -= 1all_apply(r, x)l >>= 1r >>= 1F(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 = 2for _ in range(LOG):push(r - 1)r <<= 1if d[r - 1] > 0:r -= 1return r - SIZ - 1N, 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] -= 1e[1] -= 1a, b, c = eg[a].append(b)g[b].append(a)siz = [1] * Nparent = [-1] * NC = [0] * Nq = [0]for i in q:for j in g[i]:parent[j] = iq.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] = INFfor a, b, c in edge:a = min(a, b, key=lambda x: siz[x])C[a] = cheavy = [0] * Nindex = [0] * Nidx = 0def dfs(i: int):global idxindex[i] = idxadd(idx, idx + 1, C[i] - INF)idx += 1if not g[i]:returnheavy[g[i][0]] = heavy[i]dfs(g[i][0])for j in g[i][1:]:heavy[j] = jdfs(j)dfs(0)rev = [-1] * Nfor i in range(N):rev[index[i]] = ivertices = Nerased = [False] * Ndef 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 verticesif erased[i]:returnerased[i] = Truevertices -= 1x = 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)