結果
| 問題 |
No.1215 都市消滅ビーム
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,114 bytes |
| コンパイル時間 | 148 ms |
| コンパイル使用メモリ | 83,036 KB |
| 実行使用メモリ | 77,236 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:00 |
| 合計ジャッジ時間 | 9,465 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | AC * 13 TLE * 1 -- * 26 |
ソースコード
import sys
# Increase recursion depth limit for deep trees, although BFS avoids stack overflow.
# The LCA part might use recursion implicitly depending on implementation details, but typically not.
# Setting it high just in case some part of the system uses deep recursion.
# sys.setrecursionlimit(200005)
def solve():
N, K = map(int, sys.stdin.readline().split())
# Read temple locations C and values D
# Cities are 1-based indexed in input, keep them as is.
C = list(map(int, sys.stdin.readline().split()))
D = list(map(int, sys.stdin.readline().split()))
# Build adjacency list for the tree
adj = {}
def add_edge(u, v):
if u not in adj: adj[u] = []
if v not in adj: adj[v] = []
adj[u].append(v)
adj[v].append(u)
for _ in range(N - 1):
u, v = map(int, sys.stdin.readline().split())
add_edge(u, v)
# If K=0 (no temples), the problem statement says X = -10^(10^10).
# However, constraints state K >= 2. So K=0 case is not possible per constraints.
# Precomputation for LCA and depths using BFS
# Determine the maximum required power of 2 for LCA jump pointers
MAX_LOG_N = (N).bit_length()
# parent[i][j] stores the 2^i-th ancestor of node j
parent = [[0] * (N + 1) for _ in range(MAX_LOG_N)]
# depth[j] stores the depth of node j (distance from root 1)
depth = [-1] * (N + 1)
# BFS queue stores tuples: (current_node, parent_node, depth_value)
queue = [(1, 0, 0)]
# Keep track of visited nodes to avoid cycles (though it's a tree)
visited = {1}
depth[1] = 0
# parent[0][1] = 0 signifies root 1 has no parent (or a dummy parent 0)
parent[0][1] = 0
head_idx = 0
while head_idx < len(queue):
curr, p, d = queue[head_idx]
head_idx += 1
# Set the immediate parent (2^0 ancestor)
parent[0][curr] = p
depth[curr] = d
# Explore neighbors
if curr in adj:
for neighbor in adj[curr]:
# Avoid going back to the parent node
if neighbor != p:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, curr, d + 1))
# Fill the parent table for LCA using dynamic programming
# Calculate 2^i-th ancestor based on 2^(i-1)-th ancestors
for i in range(1, MAX_LOG_N):
for j in range(1, N + 1):
# The 2^i-th ancestor of j is the 2^(i-1)-th ancestor of its 2^(i-1)-th ancestor.
# Check if the intermediate ancestor exists (is not 0)
if parent[i-1][j] != 0:
parent[i][j] = parent[i - 1][parent[i - 1][j]]
# LCA function using binary lifting
def lca(u, v):
# Ensure u and v are valid nodes
if u == 0 or v == 0: return 0
# Ensure u is the deeper node (or equal depth)
if depth[u] < depth[v]:
u, v = v, u
# Lift node u up to the same depth as v
diff = depth[u] - depth[v]
# Use bit manipulation to check powers of 2
for i in range(MAX_LOG_N):
if (diff >> i) & 1:
u = parent[i][u]
# If u and v are the same node now, it's the LCA
if u == v:
return u
# Lift both u and v simultaneously keeping them below the LCA
# Iterate from largest power of 2 down to 0
for i in range(MAX_LOG_N - 1, -1, -1):
# If 2^i-th parents are different, lift both nodes
if parent[i][u] != parent[i][v]:
u = parent[i][u]
v = parent[i][v]
# After the loop, u and v are direct children of the LCA
# The LCA is the immediate parent of u (or v)
return parent[0][u]
# Define a sentinel value for the case of no temples.
# Choose a value smaller than any possible X. Min possible X can be approx -K * 10^9 + 0.
# So -10^5 * 10^9 = -10^14. A value like -2 * 10^18 is safe.
SENTINEL = -3 * 10**18
# Store calculated X values for all possible operations
X_values = []
# Helper function to compute X for a given set of temple indices (0-based)
def compute_X(temple_indices):
# If no temples remain, return sentinel value
if not temple_indices:
return SENTINEL
# Get the list of cities where remaining temples are located
current_cities = [C[i] for i in temple_indices]
# Calculate the sum of values of remaining temples
current_S = sum(D[i] for i in temple_indices)
# Compute the LCA of all cities with remaining temples
# Start with the first city
current_T = current_cities[0]
# Iteratively compute LCA with subsequent cities
for idx in range(1, len(current_cities)):
current_T = lca(current_T, current_cities[idx])
# Handle potential issue if LCA returns 0 (should not happen for valid tree and nodes 1..N)
if current_T == 0:
# This might indicate an issue, return sentinel or handle error appropriately
# Depending on tree structure, lca(1, node) = 1.
# If LCA logic is correct, this shouldn't happen unless graph disconnected or nodes outside 1..N used.
return SENTINEL # Indicate error/undefined state
# Final X value is sum S + depth of LCA node T
# Ensure current_T is within valid range [1, N] before accessing depth
if not (1 <= current_T <= N):
return SENTINEL # Error case
return current_S + depth[current_T]
# Case 0: No removal of temples
# All temples initially present. Indices are 0 to K-1.
X_values.append(compute_X(list(range(K))))
# Cases 1 to K*(K+1)/2: Removing temples with index from l to r (inclusive)
# Temple indices are 1-based in problem statement, l and r are 1-based.
for l in range(1, K + 1): # l loops from 1 to K
for r in range(l, K + 1): # r loops from l to K
# Determine indices of remaining temples (0-based)
current_temples_indices = []
for i in range(K): # i is the 0-based index
# The problem refers temple indices 1..K. So temple `i+1` is considered.
# Check if temple `i+1` is NOT in the range [l, r] to be removed.
if not (l <= i + 1 <= r):
current_temples_indices.append(i)
# Compute X for the remaining temples
X_values.append(compute_X(current_temples_indices))
# Sort all computed X values
X_values.sort()
# The total number of operations is K*(K+1)/2 + 1.
# The median is the element at rank floor((total_count + 1) / 2).
# Calculate the 0-based index for the median value.
total_count = len(X_values)
median_idx = (total_count + 1) // 2 - 1
# Print the median value
print(X_values[median_idx])
# Call the main solver function
solve()