結果
| 問題 | No.2439 Fragile Apple Tree |
| ユーザー |
 tassei903
|
| 提出日時 | 2023-08-12 03:10:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,631 bytes |
| コンパイル時間 | 422 ms |
| コンパイル使用メモリ | 82,164 KB |
| 実行使用メモリ | 235,844 KB |
| 最終ジャッジ日時 | 2024-05-02 11:38:15 |
| 合計ジャッジ時間 | 108,095 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | AC | 2,262 ms
221,544 KB |
| testcase_04 | AC | 3,905 ms
219,380 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | AC | 7,866 ms
220,456 KB |
| testcase_08 | WA | - |
| testcase_09 | AC | 73 ms
71,516 KB |
| testcase_10 | AC | 84 ms
70,144 KB |
| testcase_11 | AC | 85 ms
70,272 KB |
| testcase_12 | AC | 81 ms
70,016 KB |
| testcase_13 | AC | 82 ms
70,016 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 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | AC | 82 ms
70,400 KB |
| testcase_29 | AC | 82 ms
69,888 KB |
| testcase_30 | AC | 83 ms
70,400 KB |
| testcase_31 | AC | 3,074 ms
235,844 KB |
| testcase_32 | AC | 2,872 ms
235,460 KB |
ソースコード
import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
"""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 nibutan(self, l: int, r: int, g: Callable[[S], bool]) -> int:
if self.prod(l, r) > 0:
return -1
return self.min_left(r, g)
class HeavyLightDecomposition(object):
def __init__(self, G, root=0):
N = len(G)
self._par = [-1] * N
self._size = [1] * N
self._heavy_child = [-1] * N
self._head = [0] * N
self._order = [0] * N
self._dfs_heavy_child(G, root)
self._dfs_decomposition(G, root)
def _dfs_heavy_child(self, G, root):
par, size, heavy_child = self._par, self._size, self._heavy_child
stack = [~root, root]
while stack:
v = stack.pop()
if v >= 0:
for nv in G[v]:
if nv != par[v]:
par[nv] = v
stack.append(~nv)
stack.append(nv)
else:
v = ~v
if par[v] != -1:
size[par[v]] += size[v]
for nv in G[v]:
if nv == par[v]:
continue
if heavy_child[v] == -1 or size[nv] > size[heavy_child[v]]:
heavy_child[v] = nv
def _dfs_decomposition(self, G, root):
par, size, heavy_child = self._par, self._size, self._heavy_child
head, order = self._head, self._order
stack = [root]
count = 0
while stack:
v = stack.pop()
order[v] = count
count += 1
if order[par[v]] == order[v] - 1:
head[v] = head[par[v]]
else:
head[v] = v
for nv in G[v]:
if nv != par[v] and nv != heavy_child[v]:
stack.append(nv)
if heavy_child[v] != -1:
stack.append(heavy_child[v])
def lca(self, u, v):
par, head, order = self._par, self._head, self._order
while True:
if order[u] > order[v]:
u, v = v, u
if head[u] == head[v]:
return u
v = par[head[v]]
def _ascend(self, u, v):
par, head, order = self._par, self._head, self._order
res = []
while head[u] != head[v]:
res.append((order[u], order[head[u]]))
u = par[head[u]]
if u != v:
res.append((order[u], order[v] + 1))
return res
def _descend(self, u, v):
return [(j, i) for i, j in self._ascend(v, u)[::-1]]
def path(self, u, v, edge=False):
l = self.lca(u, v)
return self._ascend(u, l) + ([] if edge else [(self._order[l], self._order[l])]) + self._descend(l, v)
def get_order(self):
return self._order
def edge_to_order(self, E):
par, order = self._par, self._order
return [order[u] if par[u] == v else order[v] for u, v in E]
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]
N, Q = map(int, input().split())
_A = [10**18] * N
G = [[] for _ in range(N)]
E = []
for _ in range(N - 1):
u, v, w = map(int, input().split())
u-=1
v-=1
G[u].append(v)
G[v].append(u)
E.append((u, v, w))
hld = HeavyLightDecomposition(G)
for u,v,w in E:
#print(u,v,hld._par[u])
if hld._par[u] == v:
_A[u] = w
else:
_A[v] = w
order = hld.get_order()
d = [-1] * N
for i in range(N):
d[order[i]] = i
A = [10**18] * N
t = 0
for i, a in zip(order, _A):
A[i] = a
# (a dot b)(x) = b(a(x))
# bh(ahx + al) + bl = ahbhx + albh + bl
def dot1(a, b):
ah, al = divmod(a, MOD)
bh, bl = divmod(b, MOD)
return (ah * bh % MOD) * MOD + (al * bh + bl) % MOD
dot2 = lambda a, b: dot1(b, a)
##############################
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
##############################
tree1 = LazySegmentTree(A, e, op, id_, mapping, composition)
tree2 = DualSegmentTree(N, lambda x, y: x + y, 0)
for i in range(N):
j = order[i]
tree2.update(j, j+1, hld._size[i])
#print(order)
for _ in range(Q):
t, *aa = map(int, input().split())
"""ans = []
for i in range(N):
ans.append(tree1.prod(i, i+1))
print(ans)"""
if t == 1:
v, x = aa
v -= 1
y = 10 ** 18
pt = hld.path(0, v)
for i, j in pt[::-1]:
if i <= j:
tree1.apply_range(i, j+1, -x)
y = min(y, tree1.prod(i, j+1))
else:
tree1.apply_range(j, i+1, -x)
y = min(y, tree1.prod(j, i+1))
#print(v, y, pt)
if y > 0:
continue
w = -2
for i, j in pt[::-1]:
if i <= j:
vv = tree1.nibutan(i, j+1, lambda x:x > 0)
else:
vv = tree1.nibutan(j, i+1, lambda x:x > 0)
if vv != -1:
w = vv-1
break
#print("!", w)
if w == -2:continue
z = tree2.get(w)
for i, j in pt:
if i <= j:
tree2.update(i, j+1, -z)
else:
tree2.update(j, i+1, -z)
b = A[w] - tree1.prod(w, w+1)
#print(v, w, b, hld.path(0, d[w]))
for i, j in hld.path(0, d[w]):
if i <= j:
v = tree1.apply_range(i, j+1, b)
else:
v = tree1.apply_range(j, i+1, b)
elif t == 2:
print(tree2.get(0))