結果
問題 | No.900 aδδitivee |
ユーザー | tktk_snsn |
提出日時 | 2023-02-01 20:19:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 747 ms / 2,000 ms |
コード長 | 4,249 bytes |
コンパイル時間 | 307 ms |
コンパイル使用メモリ | 87,080 KB |
実行使用メモリ | 127,008 KB |
最終ジャッジ日時 | 2023-09-14 06:20:19 |
合計ジャッジ時間 | 20,163 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 212 ms
84,052 KB |
testcase_01 | AC | 212 ms
84,304 KB |
testcase_02 | AC | 214 ms
84,504 KB |
testcase_03 | AC | 219 ms
84,516 KB |
testcase_04 | AC | 215 ms
85,052 KB |
testcase_05 | AC | 215 ms
84,584 KB |
testcase_06 | AC | 215 ms
84,864 KB |
testcase_07 | AC | 737 ms
118,560 KB |
testcase_08 | AC | 737 ms
118,360 KB |
testcase_09 | AC | 738 ms
118,316 KB |
testcase_10 | AC | 747 ms
118,592 KB |
testcase_11 | AC | 725 ms
117,992 KB |
testcase_12 | AC | 719 ms
118,348 KB |
testcase_13 | AC | 721 ms
118,388 KB |
testcase_14 | AC | 717 ms
118,288 KB |
testcase_15 | AC | 720 ms
118,236 KB |
testcase_16 | AC | 719 ms
118,020 KB |
testcase_17 | AC | 728 ms
118,520 KB |
testcase_18 | AC | 737 ms
118,500 KB |
testcase_19 | AC | 743 ms
118,536 KB |
testcase_20 | AC | 719 ms
118,424 KB |
testcase_21 | AC | 712 ms
118,392 KB |
testcase_22 | AC | 607 ms
126,924 KB |
testcase_23 | AC | 640 ms
126,980 KB |
testcase_24 | AC | 633 ms
126,900 KB |
testcase_25 | AC | 616 ms
126,668 KB |
testcase_26 | AC | 623 ms
126,860 KB |
testcase_27 | AC | 628 ms
126,856 KB |
testcase_28 | AC | 644 ms
127,008 KB |
ソースコード
import sys import os import inspect input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) if os.getenv("TKTKLOCAL", False): def debug(*arg, sep=" ", end="\n"): print(*arg, sep=sep, end=end, file=sys.stderr) def debug_indent(*arg, sep=" ", end="\n", indent=" "): frame = inspect.currentframe().f_back par_func = inspect.getframeinfo(frame).function if par_func == "<module>": debug(*arg, sep=sep, end=end) return frame_stack = inspect.stack() if len(frame_stack) > 30: return depth = sum(f.function == par_func for f in frame_stack) debug(indent * (depth - 1), end="") debug(*arg, sep=sep, end=end) else: def debug(*arg, **kwarg): pass def debug_indent(*arg, **kwarg): pass class FenwickTree(object): def __init__(self, n): self.n = n self.log = n.bit_length() self.data = [0] * n def _sum(self, r): s = 0 while r > 0: s += self.data[r - 1] r -= r & -r return s def add(self, p, x): """ a[p] += xを行う""" p += 1 while p <= self.n: self.data[p - 1] += x p += p & -p def sum(self, l, r): """a[l] + a[l+1] + .. + a[r-1]を返す""" return self._sum(r) - self._sum(l) def lower_bound(self, x): """a[0] + a[1] + .. a[i] >= x となる最小のiを返す""" if x <= 0: return -1 i = 0 k = 1 << self.log while k: if i + k <= self.n and self.data[i + k - 1] < x: x -= self.data[i + k - 1] i += k k >>= 1 return i def __repr__(self): res = [self.sum(i, i+1) for i in range(self.n)] return " ".join(map(str, res)) class FenwickTree_rangeADDrangeSUM: def __init__(self, n) -> None: self.n = n self.bit0 = FenwickTree(n) self.bit1 = FenwickTree(n) def range_add(self, l, r, x): """ add x to A[l, r) """ self.bit0.add(l, -x * l) self.bit0.add(r, x * r) self.bit1.add(l, x) self.bit1.add(r, -x) def add(self, p, x): """ add x to A[p] """ self.range_add(p, p+1, x) def __sum(self, r): return self.bit1._sum(r) * r + self.bit0._sum(r) def sum(self, l, r): """ get sum A[l, r) """ return self.__sum(r) - self.__sum(l) def __repr__(self): res = [self.sum(i, i+1) for i in range(self.n)] return " ".join(map(str, res)) def main(): N = int(input()) G = [[] for _ in range(N)] par = [-1] * N dist = [0] * N for _ in range(N - 1): a, b, w = map(int, input().split()) G[a].append((b, w)) par[b] = a dist[b] = w iter = [0] * N go_from = [-1] * N go_to = [-1] * N back_from = [-1] * N back_to = [-1] * N memo_go = [] memo_back = [] go_from[0] = 0 back_from[0] = 0 que = [0] while que: s = que[-1] if iter[s] < len(G[s]): t, d = G[s][iter[s]] iter[s] += 1 que.append(t) memo_go.append(d) go_from[t] = len(memo_go) back_from[t] = len(memo_back) else: que.pop() go_to[s] = len(memo_go) back_to[s] = len(memo_back) memo_back.append(dist[s]) debug() debug(memo_go) debug(go_from) debug(go_to) debug() debug(memo_back) debug(back_from) debug(back_to) bit_go = FenwickTree_rangeADDrangeSUM(N) bit_back = FenwickTree_rangeADDrangeSUM(N) for i, d in enumerate(memo_go): bit_go.add(i, d) for i, d in enumerate(memo_back): bit_back.add(i, d) Q = int(input()) for _ in range(Q): flag, *arg = map(int, input().split()) if flag == 1: a, x = arg bit_go.range_add(go_from[a], go_to[a], x) bit_back.range_add(back_from[a], back_to[a], x) else: a, = arg print(bit_go.sum(0, go_from[a]) - bit_back.sum(0, back_from[a])) main()