#904053 (PyPy3) No.2439 Fragile Apple Tree

提出ソース

結果

問題	No.2439 Fragile Apple Tree
ユーザー	tassei903
提出日時	2023-08-15 04:41:32
言語	PyPy3 (7.3.15)
結果	AC
実行時間	7,684 ms / 10,000 ms
コード長	15,013 bytes
コンパイル時間	279 ms
コンパイル使用メモリ	82,688 KB
実行使用メモリ	254,168 KB
最終ジャッジ日時	2024-11-23 08:43:49
合計ジャッジ時間	95,673 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3,445 ms 181,520 KB
testcase_01	AC	5,583 ms 220,172 KB
testcase_02	AC	5,142 ms 220,156 KB
testcase_03	AC	1,472 ms 234,288 KB
testcase_04	AC	2,595 ms 229,100 KB
testcase_05	AC	4,739 ms 220,252 KB
testcase_06	AC	5,225 ms 220,392 KB
testcase_07	AC	6,932 ms 218,816 KB
testcase_08	AC	7,416 ms 218,532 KB
testcase_09	AC	66 ms 70,784 KB
testcase_10	AC	65 ms 70,912 KB
testcase_11	AC	66 ms 70,528 KB
testcase_12	AC	68 ms 70,784 KB
testcase_13	AC	69 ms 70,528 KB
testcase_14	AC	7,684 ms 207,792 KB
testcase_15	AC	3,421 ms 216,260 KB
testcase_16	AC	5,111 ms 221,252 KB
testcase_17	AC	5,226 ms 220,648 KB
testcase_18	AC	1,793 ms 182,896 KB
testcase_19	AC	2,206 ms 133,044 KB
testcase_20	AC	1,265 ms 123,736 KB
testcase_21	AC	970 ms 88,504 KB
testcase_22	AC	3,538 ms 149,560 KB
testcase_23	AC	1,918 ms 115,332 KB
testcase_24	AC	1,908 ms 128,412 KB
testcase_25	AC	1,346 ms 164,596 KB
testcase_26	AC	1,620 ms 175,500 KB
testcase_27	AC	1,510 ms 145,448 KB
testcase_28	AC	67 ms 70,528 KB
testcase_29	AC	64 ms 70,400 KB
testcase_30	AC	71 ms 71,168 KB
testcase_31	AC	2,684 ms 254,168 KB
testcase_32	AC	2,677 ms 253,844 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code


"""Buggy! the output of practice_k becomes about 1/4."""
from typing import Callable, List, TypeVar

S = TypeVar("S")
F = TypeVar("F")

MOD = 998244353


class LazySegmentTree:
    """Lazy Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = [
        "e",
        "op",
        "id",
        "mapping",
        "composition",
        "_n",
        "_log",
        "_size",
        "tree",
        "lazy",
    ]

    def __init__(
        self,
        a: List[S],
        e: S,
        op: Callable[[S, S], S],
        id_: F,
        mapping: Callable[[F, S], S],
        composition: Callable[[F, F], F],
    ) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        return self.tree[k]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        if l == r:
            return self.e

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)

        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        if l == r:
            return

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)

    def max_right(self, l: int, g: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert g(self.e)

        if l == self._n:
            return self._n

        l += self._size
        for i in range(self._log, 0, -1):
            self._push(l >> i)
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not g(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if g(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, g: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert g(self.e)

        if not r:
            return 0

        r += self._size
        for i in range(self._log, 0, -1):
            self._push((r - 1) >> i)
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not g(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if g(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            sm = self.op(self.tree[r], sm)

            if (r & -r) == r:
                break

        return 0
    def min_left(self,r,g):
        assert (0<=r and r<=self._n)
        assert g(self.e)
        if r==0:return 0
        r+=self._size
        for i in range(self._log,0,-1):self._push((r-1)>>i)
        sm=self.e
        while(1):
            r-=1
            while(r>1 and (r%2)):r>>=1
            if not(g(self.op(self.tree[r],sm))):
                while(r<self._size):
                    self._push(r)
                    r=(2*r+1)
                    if g(self.op(self.tree[r],sm)):
                        sm=self.op(self.tree[r],sm)
                        r-=1
                return r+1-self._size
            sm=self.op(self.tree[r],sm)
            if (r&-r)==r:break
        return 0
    
    def nibutan_query(self, l, r) -> int:
        if self.prod(l, r) > 0:
            return -1
        res =  self.min_left(r, lambda x:x>0)

        return res-1
    
            

class DualSegmentTree:
    def __init__(self, size, f, default):
        self.n = (size-1).bit_length()
        self.size = 1<<self.n
        self.default = default
        self.lazy = [default]*(self.size*2)
        self.f = f

    def propagate(self, k):
        lazy = self.lazy
        if lazy[k] != self.default:
            lazy[2*k] = self.f(lazy[2*k], lazy[k])
            lazy[2*k+1] = self.f(lazy[2*k+1], lazy[k])
            lazy[k] = self.default

    def thrust(self, k):
        for i in range(self.n,0,-1):
            self.propagate(k>>i)

    def update(self, a, b, x):
        a += self.size
        b += self.size-1
        self.thrust(a)
        self.thrust(b)
        l = a
        r = b + 1
        lazy = self.lazy
        while l < r:
            if l & 1:
                lazy[l] = self.f(lazy[l], x)
                l += 1
            if r & 1:
                r -= 1
                lazy[r] = self.f(lazy[r], x)
            l >>= 1
            r >>= 1
    
    def get(self, k):
        k += self.size
        self.thrust(k)
        return self.lazy[k]

class HLD:
    def __init__(self, n):
        self.g = [[] for _ in range(n)]
        self.sz = [1] * n
        self.in_ = [0] * n
        self.out = [0] * n
        self.head = [0] * n
        self.rev = [0] * n
        self.par = [0] * n
        self.dep = [0] * n
    
    def dfs_sz(self, a, p, b):
        self.par[a] = p
        self.sz[a] = 1
        self.dep[a] = b
        if self.g[a] and self.g[a][0] == p:
            self.g[a][0], self.g[a][-1] = self.g[a][-1], self.g[a][0]
        for to in self.g[a]:
            if to == p:
                continue
            self.dfs_sz(to, a, b + 1)
            self.sz[a] += self.sz[to]
            if self.sz[self.g[a][0]] < self.sz[to]:
                self.g[a][0], to = to, self.g[a][0]
    
    def dfs_hld(self, a, p, t):
        self.in_[a] = t[0]
        self.rev[t[0]] = a
        t[0] += 1
        for to in self.g[a]:
            if to == p:
                continue
            self.head[to] = self.head[a] if self.g[a][0] == to else to
            self.dfs_hld(to, a, t)
        self.out[a] = t[0]


    def dfs_sz(self, v):
        stack = [v]
        while stack:
            v = stack.pop()
            if v >= 0:
                if len(self.g[v]) >= 2 and self.g[v][-1] == self.par[v]:
                    self.g[v][-1], self.g[v][-2] = self.g[v][-2], self.g[v][-1]
                for i, nv in enumerate(self.g[v]):
                    if nv == self.par[v]:
                        continue
                    self.dep[nv] = self.dep[v] + 1
                    self.par[nv] = v
                    stack.append(i)
                    stack.append(~nv)
                    stack.append(nv)
            else:
                nv = ~v
                v = self.par[nv]
                i = stack.pop()
                self.sz[v] += self.sz[nv]
                if self.sz[nv] > self.sz[self.g[v][-1]]:
                    self.g[v][-1], self.g[v][i] = self.g[v][i], self.g[v][-1]
        
    def dfs_hld(self, v):
        id = 0
        stack = [~v, v]
        while stack:
            v = stack.pop()
            if v >= 0:
                self.in_[v] = id
                id += 1
                for nv in self.g[v]:
                    if nv == self.par[v]:
                        continue
                    if nv == self.g[v][-1]:
                        self.head[nv] = self.head[v]
                    else:
                        self.head[nv] = nv
                    stack.append(~nv)
                    stack.append(nv)
            else:
                self.out[~v] = id
        for i in range(len(self.g)):
            self.rev[self.in_[i]] = i
                

    
    def edgeset(self, a, b):
        self.g[a].append(b)
        self.g[b].append(a)
    
    def build(self):
        self.dfs_sz(0)
        self.dfs_hld(0)
    
    def input(self, n):
        for _ in range(n - 1):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            self.edgeset(a, b)
        self.build()
    
    def la(self, a, x):
        while True:
            h = self.head[a]
            if self.in_[a] - x >= self.in_[h]:
                return self.rev[self.in_[a] - x]
            x -= self.in_[a] - self.in_[h] + 1
            a = self.par[h]
    
    def lca(self, a, b):
        while True:
            if self.in_[a] > self.in_[b]:
                a, b = b, a
            if self.head[a] == self.head[b]:
                return a
            b = self.par[self.head[b]]
    
    def query(self, a, b, ti, q, f, edge=False):
        l = ti
        r = ti
        while True:
            
            if self.in_[a] > self.in_[b]:
                a, b = b, a
                l, r = r, l
            if self.head[a] == self.head[b]:
                break
            l = f(q(self.in_[self.head[b]], self.in_[b] + 1), l)
            b = self.par[self.head[b]]
        return f(f(q(self.in_[a] + edge, self.in_[b] + 1), l), r)
    
    def nibutan(self, a, b, q, edge=False):
        while True:
            if self.in_[a] > self.in_[b]:
                a, b = b, a
            if self.head[a] == self.head[b]:
                break
            res = q(self.in_[self.head[b]], self.in_[b] + 1)
            if res != -1:
                return self.rev[res]
            b = self.par[self.head[b]]
        res = q(self.in_[a] + edge, self.in_[b] + 1)
        if res != -1:
            return self.rev[res]
        return -1
    
    def addpath(self, a, b, x, q, edge=False):
        while True:
            if self.in_[a] > self.in_[b]:
                a, b = b, a
            if self.head[a] == self.head[b]:
                break
            q(self.in_[self.head[b]], self.in_[b] + 1, x)
            b = self.par[self.head[b]]

        q(self.in_[a] + edge, self.in_[b] + 1, x)
    
    def addst(self, a, x, q):
        q(self.in_[a], self.out[a], x)
e = 10**18
id_ = 0

def op(s, t):
    return min(s, t)

def mapping(f, a):
    return a + f

def composition(f, g):
    return f + g
inf = 10**18
# Main code
N, Q = map(int, input().split())
ans = N
edges = []
init_c = [-1] * N
hld = HLD(N)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append([a, b, c])
    hld.edgeset(a, b )

hld.build()

A = [-1] * N
seg2 = DualSegmentTree(N, lambda x,y: x+ y, 0)

for i in range(N - 1):
    if hld.dep[edges[i][0]] > hld.dep[edges[i][1]]:
        edges[i][0], edges[i][1] = edges[i][1], edges[i][0]
    A[hld.in_[edges[i][1]]] = edges[i][2]
    init_c[edges[i][1]] = edges[i][2]


init_c[0] = inf
A[hld.in_[0]] = inf

seg = LazySegmentTree(A, inf, op, id_, mapping, composition)

for i in range(N):
    seg2.update(hld.in_[i], hld.in_[i]+1, hld.sz[i])

for _ in range(Q):
    type_, *rest = map(int, input().split())
    if type_ == 1:
        v, x = rest
        v -= 1
        hld.addpath(0, v, -x, lambda a, b, x: seg.apply_range(a, b, x))

        w = hld.nibutan(0, v, lambda a, b: seg.nibutan_query(a, b))
        if w == -1:
            continue
        subtree_sz = seg2.get(hld.in_[w])
        ans -= subtree_sz
        hld.addpath(0, hld.par[w], -subtree_sz, lambda a, b, x: seg2.update(a, b, x))
        w_apple = init_c[w] - seg.prod(hld.in_[w], hld.in_[w]+1)
        hld.addpath(0, w, w_apple, lambda a, b, x: seg.apply_range(a, b, x))
    if type_ == 2:
        print(ans)

yukicoder

結果

テストケース

ソースコード