結果
問題 | No.900 aδδitivee |
ユーザー | Kiri8128 |
提出日時 | 2019-10-05 16:18:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 674 ms / 2,000 ms |
コード長 | 1,748 bytes |
コンパイル時間 | 277 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 115,712 KB |
最終ジャッジ日時 | 2024-04-15 21:56:59 |
合計ジャッジ時間 | 15,886 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
54,656 KB |
testcase_01 | AC | 44 ms
54,784 KB |
testcase_02 | AC | 49 ms
56,832 KB |
testcase_03 | AC | 49 ms
56,320 KB |
testcase_04 | AC | 49 ms
56,576 KB |
testcase_05 | AC | 49 ms
56,576 KB |
testcase_06 | AC | 49 ms
56,192 KB |
testcase_07 | AC | 674 ms
110,216 KB |
testcase_08 | AC | 629 ms
110,080 KB |
testcase_09 | AC | 659 ms
110,468 KB |
testcase_10 | AC | 632 ms
109,696 KB |
testcase_11 | AC | 645 ms
109,928 KB |
testcase_12 | AC | 664 ms
110,080 KB |
testcase_13 | AC | 653 ms
109,992 KB |
testcase_14 | AC | 634 ms
109,824 KB |
testcase_15 | AC | 637 ms
109,824 KB |
testcase_16 | AC | 643 ms
109,856 KB |
testcase_17 | AC | 660 ms
109,872 KB |
testcase_18 | AC | 631 ms
109,952 KB |
testcase_19 | AC | 643 ms
109,824 KB |
testcase_20 | AC | 642 ms
110,196 KB |
testcase_21 | AC | 647 ms
110,336 KB |
testcase_22 | AC | 568 ms
115,328 KB |
testcase_23 | AC | 550 ms
115,052 KB |
testcase_24 | AC | 560 ms
115,328 KB |
testcase_25 | AC | 566 ms
115,104 KB |
testcase_26 | AC | 556 ms
115,200 KB |
testcase_27 | AC | 573 ms
115,712 KB |
testcase_28 | AC | 555 ms
115,072 KB |
ソースコード
NN = 17 BIT=[0]*(2**NN+1) BIT2=[0]*(2**NN+1) def addrange(l0, r0, x=1): l, r = l0, r0 while l <= 2**NN: BIT[l] += x l += l & (-l) while r <= 2**NN: BIT[r] -= x r += r & (-r) def getvalue(r): a = 0 while r != 0: a += BIT[r] r -= r&(-r) return a def addrange2(l0, r0, x=1): l, r = l0, r0 while l <= 2**NN: BIT2[l] += x l += l & (-l) while r <= 2**NN: BIT2[r] -= x r += r & (-r) def getvalue2(r): a = 0 while r != 0: a += BIT2[r] r -= r&(-r) return a N = int(input()) X = [[] for i in range(N)] for i in range(N-1): x, y, d = map(int, input().split()) X[x].append((y, d)) X[y].append((x, d)) P = [(-1, 0)] * N Q = [(-1, 0), (0, 0)] ET = [] ct = 0 dd = 0 CTA = [0] * N CTB = [0] * N DE = [0] * N D = [0] * N de = -1 while Q: i, d = Q.pop() if i < 0: CTB[~i] = ct de -= 1 dd -= d continue if i >= 0: ct += 1 if CTA[i] == 0: CTA[i] = ct dd += d de += 1 DE[i] = de D[i] = dd for a, d in X[i][::-1]: if a != P[i][0]: ET.append((i, a)) P[a] = (i, d) for k in range(len(X[a])): if X[a][k][0] == i: del X[a][k] break Q.append((~a, d)) Q.append((a, d)) for _ in range(int(input())): tmp = [int(a) for a in input().split()] if tmp[0] == 1: a, x = tmp[1:] addrange(CTA[a]+1, CTB[a]+1, x) addrange2(CTA[a]+1, CTB[a]+1, x * DE[a]) else: b = tmp[1] print(D[b] + getvalue(CTA[b]) * DE[b] - getvalue2(CTA[b]))