結果

問題 No.1524 Upward Mobility
コンテスト
ユーザー gorugo30
提出日時 2021-05-28 22:18:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,904 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 117,972 KB
最終ジャッジ日時 2024-11-07 09:47:52
合計ジャッジ時間 12,519 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 11 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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