結果
| 問題 |
No.1998 Manhattan Restaurant
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,441 bytes |
| コンパイル時間 | 247 ms |
| コンパイル使用メモリ | 82,772 KB |
| 実行使用メモリ | 77,860 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:16 |
| 合計ジャッジ時間 | 6,091 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 11 TLE * 1 -- * 19 |
ソースコード
import sys
# Set higher recursion depth limit if needed for deep graph traversals, although BFS is iterative.
# sys.setrecursionlimit(200000)
def solve():
# Read the number of houses
N = int(sys.stdin.readline())
# Handle base cases: If N is 0 or 1, the minimum max distance is 0.
# The problem guarantees N >= 1, so N=0 check is mostly for completeness.
if N <= 1:
print(0)
# Consume coordinate line if N=1
if N == 1:
sys.stdin.readline()
return
# Read house coordinates from input
pts_coords = []
for _ in range(N):
pts_coords.append(list(map(int, sys.stdin.readline().split())))
# Transform coordinates from (X, Y) to (U, V) = (X+Y, X-Y).
# This transformation maps Manhattan distance in (X, Y) plane to
# Chebyshev distance (L_infinity) in (U, V) plane.
# L1((x1,y1), (x2,y2)) = |x1-x2| + |y1-y2|
# L_inf((u1,v1), (u2,v2)) = max(|u1-u2|, |v1-v2|)
# where u1=x1+y1, v1=x1-y1 and u2=x2+y2, v2=x2-y2.
U = [(pts_coords[i][0] + pts_coords[i][1]) for i in range(N)]
V = [(pts_coords[i][0] - pts_coords[i][1]) for i in range(N)]
# Find indices of points with minimum/maximum U and V coordinates.
# These points are called "extremal" points. They define the bounding box of the point set in (U, V) space.
min_U_idx, max_U_idx = 0, 0
min_V_idx, max_V_idx = 0, 0
# Store the actual min/max coordinate values found so far to avoid recomputing U[idx] repeatedly.
current_min_U, current_max_U = U[0], U[0]
current_min_V, current_max_V = V[0], V[0]
# Iterate through points to find the indices corresponding to extremal coordinates.
for i in range(1, N):
if U[i] < current_min_U: current_min_U = U[i]; min_U_idx = i
if U[i] > current_max_U: current_max_U = U[i]; max_U_idx = i
if V[i] < current_min_V: current_min_V = V[i]; min_V_idx = i
if V[i] > current_max_V: current_max_V = V[i]; max_V_idx = i
# Collect the unique indices of the extremal points. There are at most 4 unique indices.
extremal_indices = {min_U_idx, max_U_idx, min_V_idx, max_V_idx}
# Define the check function used in binary search.
# It returns True if it's possible to place two restaurants such that the maximum distance
# from any house to its nearest restaurant is at most D.
def check(D):
# K = 2D is the maximum allowed span (range width/height) of U and V coordinates within a cluster/group.
# A set of points can be covered by one restaurant R if there exists R' = (u, v) such that
# max(|Ui - u|, |Vi - v|) <= D for all points i in the set.
# This is possible if and only if (max Ui - min Ui <= 2D) and (max Vi - min Vi <= 2D).
K = 2 * D
# Adjacency list for the restricted graph G'.
# G' is constructed based on the "far apart" relationship, but only considering pairs
# involving at least one extremal point.
adj = [[] for _ in range(N)]
# Use a set to efficiently track edges added to avoid duplicates in adjacency lists
# and redundant checks.
edges_added = set()
# Build the restricted graph G'
# Iterate through all points i
for i in range(N):
# Check pairs (i, ext_idx) where ext_idx is an extremal point index
for ext_idx in extremal_indices:
# Skip self-loops (a point paired with itself)
if i == ext_idx: continue
# Process each pair {i, ext_idx} only once. Use a sorted tuple as a canonical representation.
pair = tuple(sorted((i, ext_idx)))
if pair in edges_added: continue # Skip if this pair has already been processed
# Check the distance condition: edge exists if points are "far apart" in U or V coordinates.
if abs(U[i] - U[ext_idx]) > K or abs(V[i] - V[ext_idx]) > K:
# Add edge between i and ext_idx in the adjacency list representation
adj[i].append(ext_idx)
adj[ext_idx].append(i)
edges_added.add(pair) # Mark this pair as processed
# Check if the constructed graph G' is bipartite using Breadth-First Search (BFS).
# Bipartiteness check also assigns colors (0 or 1) to nodes, representing the two sets (potential clusters).
colors = {} # Dictionary to store assigned color for visited nodes during BFS
is_bipartite = True
# Iterate through all nodes to handle potentially disconnected graphs
for i in range(N):
# Start BFS from node i if it hasn't been visited (colored) yet
if i not in colors:
colors[i] = 0 # Assign an initial color (e.g., 0)
q = [i] # Initialize BFS queue with the starting node
head = 0 # Use head index to simulate queue dequeuing efficiently
while head < len(q):
curr = q[head]
head += 1
# Process neighbors of the current node
for neighbor in adj[curr]:
if neighbor not in colors:
# If neighbor is uncolored, assign the opposite color and add to queue
colors[neighbor] = 1 - colors[curr]
q.append(neighbor)
elif colors[neighbor] == colors[curr]:
# Conflict detected: an edge connects two nodes of the same color.
# This means an odd cycle exists, so the graph is not bipartite.
is_bipartite = False
break # Exit neighbor loop immediately
if not is_bipartite:
break # Exit BFS loop for the current component
if not is_bipartite:
break # Exit the main loop over nodes since non-bipartiteness is confirmed
# If G' is not bipartite, then the distance D is too small, return False
if not is_bipartite:
return False
# If G' is bipartite, we proceed to verify the span conditions for the partition found.
# This partition is derived from the BFS coloring.
C1_indices = [] # List to store indices of points assigned to cluster 1 (color 0)
C2_indices = [] # List to store indices of points assigned to cluster 2 (color 1)
# Assign nodes to clusters C1 and C2 based on their assigned colors.
# Nodes that were not visited by BFS (e.g., isolated vertices or entire components)
# need to be assigned as well. We can arbitrarily assign them to C1.
for i in range(N):
if i in colors: # If node i was colored during BFS
if colors[i] == 0:
C1_indices.append(i)
else:
C2_indices.append(i)
else:
# Assign uncolored nodes to C1 (this handles isolated nodes/components)
colors[i] = 0 # Record the assignment for consistency
C1_indices.append(i)
# Check span condition for cluster C1
if C1_indices: # Only check if the cluster is non-empty
# Compute the bounding box (min/max U and V coordinates) for points in C1
min_U1 = U[C1_indices[0]]
max_U1 = U[C1_indices[0]]
min_V1 = V[C1_indices[0]]
max_V1 = V[C1_indices[0]]
# Optimize finding min/max by iterating from the second element
for idx in C1_indices[1:]:
u_val, v_val = U[idx], V[idx]
min_U1 = min(min_U1, u_val)
max_U1 = max(max_U1, u_val)
min_V1 = min(min_V1, v_val)
max_V1 = max(max_V1, v_val)
# Check if the U-span (maxU - minU) or V-span (maxV - minV) exceeds the threshold K
if max_U1 - min_U1 > K or max_V1 - min_V1 > K:
return False # Span condition failed for C1
# Check span condition for cluster C2
if C2_indices: # Only check if the cluster is non-empty
# Compute the bounding box for points in C2
min_U2 = U[C2_indices[0]]
max_U2 = U[C2_indices[0]]
min_V2 = V[C2_indices[0]]
max_V2 = V[C2_indices[0]]
# Optimize finding min/max
for idx in C2_indices[1:]:
u_val, v_val = U[idx], V[idx]
min_U2 = min(min_U2, u_val)
max_U2 = max(max_U2, u_val)
min_V2 = min(min_V2, v_val)
max_V2 = max(max_V2, v_val)
# Check if the U-span or V-span exceeds the threshold K
if max_U2 - min_U2 > K or max_V2 - min_V2 > K:
return False # Span condition failed for C2
# If both G' bipartiteness and span conditions for the partition hold, D is feasible.
return True
# Perform binary search on the answer D. The answer is guaranteed to be an integer.
low = 0 # Minimum possible distance is 0
# Calculate an initial upper bound for D.
# The maximum distance needed if all points were covered by a single restaurant is ceil(max_span / 2).
# This serves as a valid upper bound for the two-restaurant case.
max_span_U = 0
if N > 0 : max_span_U = current_max_U - current_min_U # Use pre-calculated min/max U values
max_span_V = 0
if N > 0 : max_span_V = current_max_V - current_min_V # Use pre-calculated min/max V values
# The upper bound is ceil(max(span_U, span_V) / 2)
high = (max(max_span_U, max_span_V) + 1) // 2
ans = high # Initialize answer with this upper bound
# Standard binary search loop to find the minimum feasible D
while low <= high:
mid = (low + high) // 2
if check(mid): # If distance `mid` is feasible
ans = mid # Store `mid` as the best answer found so far
high = mid - 1 # Try to find an even smaller feasible D
else: # If distance `mid` is not feasible
low = mid + 1 # Need a larger D to satisfy conditions
# Output the minimum feasible distance D found
print(ans)
# Execute the solve function to run the program
solve()