結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2020-02-29 21:00:45 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,680 ms / 2,000 ms |
コード長 | 1,828 bytes |
コンパイル時間 | 84 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 56,244 KB |
最終ジャッジ日時 | 2024-10-13 20:18:53 |
合計ジャッジ時間 | 14,765 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#!/usr/bin/env python3# %%import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlines# %%N, *A = map(int, read().split())# %%graph = [[] for _ in range(N + 1)]for i, x in enumerate(A, 2):x += 1graph[i].append(x)graph[x].append(i)# %%class BinaryIndexedTree():def __init__(self, seq):self.size = len(seq)self.depth = self.size.bit_length()self.build(seq)def build(self, seq):data = seqsize = self.sizefor i, x in enumerate(data):j = i + (i & (-i))if j < size:data[j] += data[i]self.data = datadef __repr__(self):return self.data.__repr__()def get_sum(self, i):data = self.datas = 0while i:s += data[i]i -= i & -ireturn sdef add(self, i, x):data = self.datasize = self.sizewhile i < size:data[i] += xi += i & -idef find_kth_element(self, k):data = self.datasize = self.sizex, sx = 0, 0dx = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):dx = (1 << i)if x + dx >= size:continuey = x + dxsy = sx + data[y]if sy < k:x, sx = y, syreturn x + 1# # %%par = [0] * (N + 1)st = [1]answer = 0bit = BinaryIndexedTree([0] * (N + 1))get_sum = bit.get_sumadd = bit.addwhile st:x = st[-1]if not graph[x]:answer += get_sum(x)add(x, -1)st.pop()continuey = graph[x].pop()if y == par[x]:continuepar[y] = xadd(y, 1)st.append(y)# %%print(answer)