結果

問題 No.1524 Upward Mobility
ユーザー gorugo30gorugo30
提出日時 2021-05-28 22:18:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,904 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 118,096 KB
最終ジャッジ日時 2024-04-25 00:23:37
合計ジャッジ時間 11,260 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 250 ms
111,884 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 338 ms
112,412 KB
testcase_11 AC 254 ms
115,772 KB
testcase_12 AC 237 ms
115,900 KB
testcase_13 AC 424 ms
116,408 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 41 ms
54,272 KB
testcase_24 AC 42 ms
53,760 KB
testcase_25 AC 41 ms
54,144 KB
testcase_26 AC 43 ms
54,016 KB
testcase_27 AC 41 ms
54,144 KB
testcase_28 AC 43 ms
53,888 KB
testcase_29 AC 198 ms
117,076 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self, n, identity, func = None, updf = None):
        self.n = 2 ** (n - 1).bit_length()
        self.data = [0] * (2 * self.n)
        self.identity = 0
        self._func = lambda x, y: max(x, y)
        self._updf = lambda x, y: x + y
    def update(self, i, x):
        i += self.n
        self.data[i] = self._updf(self.data[i], x)
        while i > 1:
            i >>= 1
            self.data[i] = self._func(self.data[i << 1], self.data[(i << 1) | 1])
    def find(self, s, t): #[s, t)
        l = s + self.n
        r = t + self.n
        lres = self.identity
        rres = self.identity
        while l < r:
            if l & 1: # 右なら
                lres = self._func(lres, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self._func(self.data[r], rres)
            l >>= 1
            r >>= 1
        return self._func(lres, rres)
N = int(input())
P = [0] + list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [[] for i in range(N)]
for i in range(N):
    A[i] -= 1
    P[i] -= 1
    if i > 0:
        C[P[i]].append(i)
m = [10 ** 9] * N
M = [-1] * N
et = []
from collections import deque
st = deque([0])
i = 0
while len(st):
    v = st.pop()
    if v < 0:
        v = ~v
        if et[-1] == v:
            continue
        et.append(v)
        m[v] = min(m[v], i)
        M[v] = max(m[v], i)
        i += 1
    else:
        et.append(v)
        m[v] = min(m[v], i)
        M[v] = max(m[v], i)
        i += 1
        for c in C[v]:
            st.append(~v)
            st.append(~c)
            st.append(c)

V = [i for i in range(N)]
V.sort(key = lambda x: -A[x])
seg = SegTree(len(et), 0)
dp = [0] * N
for v in V:
    for c in C[v]:
        dp[v] += seg.find(m[c], M[c] + 1)
    dp[v] += B[v]
    seg.update(m[v], dp[v])
print(max(dp))
0