結果
問題 | No.2439 Fragile Apple Tree |
ユーザー |
![]() |
提出日時 | 2023-08-18 19:50:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,240 ms / 10,000 ms |
コード長 | 3,178 bytes |
コンパイル時間 | 894 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 195,768 KB |
最終ジャッジ日時 | 2024-11-28 10:05:43 |
合計ジャッジ時間 | 51,069 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
# パス減算 → 破壊チェック → 破壊された辺に掛かっていた重みを上にパス加算# 必要な操作: 辺属性, パス加算, 区間 min の max-right, 1 辺取得import syssys.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)L = lR = rwhile L < R:if L & 1:all_apply(L, x)L += 1if R & 1:R -= 1all_apply(R, x)L >>= 1R >>= 1for 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].append(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 = 0q = [0]while q:i = q.pop()index[i] = idxadd(idx, idx + 1, C[i] - INF)idx += 1if not g[i]:continuefor j in g[i]:heavy[j] = jheavy[g[i][-1]] = heavy[i]q.extend(g[i])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):q = [i]global verticeswhile q:i = q.pop()if erased[i]:continueerased[i] = Truevertices -= 1x = C[i] - get(index[i])add(index[i], index[i] + 1, INF)q.extend(g[i])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)