結果
| 問題 |
No.1777 万華鏡美術館
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:57:06 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,576 bytes |
| コンパイル時間 | 142 ms |
| コンパイル使用メモリ | 82,884 KB |
| 実行使用メモリ | 77,784 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:00 |
| 合計ジャッジ時間 | 1,408 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 1 WA * 9 |
ソースコード
import sys
# Increase recursion depth limit for safety, although the main loop is iterative.
# sys.setrecursionlimit(200000)
def solve():
N, M = map(int, sys.stdin.readline().split())
# Handle the special case identified for C3 (N=3, M=0).
# This case requires 5 colors based on vertex-face coloring constraints analysis.
if N == 3 and M == 0:
print(5)
return
# Use a dictionary for the adjacency list to handle vertices 1 to N.
adj = {}
for i in range(1, N + 1):
adj[i] = []
# Add the base structure: edges connecting adjacent pillars on the circle.
for i in range(1, N):
adj[i].append(i + 1)
adj[i+1].append(i)
# Connect pillar N back to pillar 1 to complete the circle.
adj[N].append(1)
adj[1].append(N)
# Initialize vertex degrees based on the circle edges. Each vertex starts with degree 2.
degrees = {}
for i in range(1, N + 1):
degrees[i] = 2 # Initially degree 2 from circle neighbors
# Process the M walls provided in the input.
# Add wall edges to the adjacency list and update vertex degrees.
# Keep track of wall edges if needed for identification later, though currently not used explicitly.
# wall_edge_pairs = set()
for _ in range(M):
u, v = map(int, sys.stdin.readline().split())
# Add edge connections for the wall.
adj[u].append(v)
adj[v].append(u)
# Increment degrees for vertices u and v.
degrees[u] = degrees.get(u, 0) + 1
degrees[v] = degrees.get(v, 0) + 1
# wall_edge_pairs.add(tuple(sorted((u,v))))
# Calculate the maximum degree among all vertices (pillars).
max_degree = 0
if degrees: # Ensure degrees dictionary is not empty
# Find max value in degrees dictionary, handle case where dict might be empty if N=0 (not possible N>=3)
max_degree = max(degrees.values()) if degrees else 0
# --- Face Finding Section ---
# The goal is to find the maximum length of any inner face boundary.
# Build adjacency lists where neighbors are ordered clockwise around each vertex.
# This is crucial for correctly traversing face boundaries.
adj_ordered = {}
for i in range(1, N + 1):
# Ensure vertex i exists in adjacency list (should always be true for 1..N)
if i not in adj: continue
# Get neighbors of vertex i. Use list(set(...)) to handle potential duplicates if any edge was added twice.
# Problem statement guarantees no multi-edges, so set() might be redundant but safe.
neighbors = list(adj[i])
# Helper function to compute clockwise distance from vertex k to vertex v.
# Assumes vertices 1..N are arranged on a circle. Uses 0-based indexing internally.
def cw_dist(k, v):
k_0 = k - 1 # Map k to 0..N-1
v_0 = v - 1 # Map v to 0..N-1
return (v_0 - k_0 + N) % N # Calculate clockwise distance using modulo arithmetic
# Identify special neighbors: vertex i+1 (clockwise) and i-1 (counter-clockwise).
node_plus_1 = (i % N) + 1
node_minus_1 = ((i - 2 + N) % N) + 1 # Correct calculation for i-1 mod N
wall_endpoints = [] # List to store neighbors connected by walls
has_node_plus_1 = False # Flag if neighbor i+1 exists
has_node_minus_1 = False # Flag if neighbor i-1 exists
processed_neighbors = set() # To avoid processing the same neighbor multiple times if list contains duplicates
for neighbor in neighbors:
if neighbor in processed_neighbors: continue
processed_neighbors.add(neighbor)
# Check if neighbor is the standard clockwise or counter-clockwise neighbor on the circle
is_standard_circle_neighbor = False
if neighbor == node_plus_1:
has_node_plus_1 = True
is_standard_circle_neighbor = True
if neighbor == node_minus_1: # Note: Use 'if', not 'elif', as node_plus_1 could equal node_minus_1 if N=2 (but N>=3 here)
has_node_minus_1 = True
is_standard_circle_neighbor = True
# If the neighbor is not a standard circle neighbor, it must be connected by a wall.
# More robust check: Check if the edge (i, neighbor) is a circle edge.
edge_pair = tuple(sorted((i, neighbor)))
p1, p2 = edge_pair
is_circle_edge = (p2 == p1 + 1) or (p1 == 1 and p2 == N)
if not is_circle_edge:
wall_endpoints.append(neighbor)
# Sort the wall endpoints based on their clockwise distance from vertex i.
wall_endpoints.sort(key=lambda v: cw_dist(i, v))
# Construct the final ordered list of neighbors: i+1, sorted wall endpoints, i-1.
ordered_neighbors = []
if has_node_plus_1:
ordered_neighbors.append(node_plus_1)
ordered_neighbors.extend(wall_endpoints) # Add sorted wall endpoints
if has_node_minus_1:
# Avoid adding i-1 if it's already present (e.g., if it was also a wall endpoint or same as i+1 for N=2)
if node_minus_1 not in ordered_neighbors:
ordered_neighbors.append(node_minus_1)
adj_ordered[i] = ordered_neighbors
# Build a lookup map for counter-clockwise (CCW) neighbors.
# ccw_neighbor_map[curr_node][prev_node] gives the next node CCW around curr_node after prev_node.
ccw_neighbor_map = {}
for i in range(1, N + 1):
# Skip if vertex i has no ordered neighbors list (should not happen for N>=3)
if i not in adj_ordered or not adj_ordered[i]: continue
ccw_neighbor_map[i] = {}
neighbors = adj_ordered[i] # Clockwise ordered list of neighbors
k = len(neighbors)
if k == 0: continue # Skip if vertex has no neighbors (degree 0)
# Create a map from neighbor value to its index in the ordered list for O(1) lookup.
neighbor_to_idx = {neighbor: idx for idx, neighbor in enumerate(neighbors)}
# For each neighbor `curr_neighbor` of `i`, find the neighbor `next_v` that is CCW to it.
for curr_neighbor in neighbors:
# Get the index of the current neighbor in the clockwise list.
prev_idx = neighbor_to_idx[curr_neighbor]
# The index of the CCW neighbor is one step back in the list (circularly).
next_v_idx = (prev_idx - 1 + k) % k
next_v = neighbors[next_v_idx]
# Store the mapping: At vertex `i`, if arrived from `curr_neighbor`, the next vertex CCW is `next_v`.
ccw_neighbor_map[i][curr_neighbor] = next_v
# --- Face Traversal Logic ---
# Use a set to keep track of directed edges that have been visited as part of a face boundary.
visited_edge_directions = set()
max_inner_face_len = 0 # Variable to store the maximum length found for any inner face.
# Iterate through all possible starting vertices and their neighbors to initiate face traversals.
for u_start_node in range(1, N + 1):
if u_start_node not in adj_ordered: continue # Skip if vertex has no ordered neighbors list.
for v_start_node in adj_ordered[u_start_node]:
# Start a new face traversal only if this directed edge (u_start_node, v_start_node) hasn't been visited yet.
if (u_start_node, v_start_node) not in visited_edge_directions:
current_face_len = 0 # Length of the current face boundary.
curr_v = v_start_node # Current vertex in traversal.
prev_v = u_start_node # Previous vertex in traversal.
# Store edges of the current face path as sorted tuples (u, v) where u < v.
# Used later to check if the face is the outer face.
path_edges = []
# Loop to trace the face boundary.
while True:
# Check if this directed edge has already been visited IN THIS traversal.
# This indicates an issue, possibly graph error or infinite loop. Break for safety.
# In a correct simple planar graph embedding, this shouldn't happen during a single face trace.
if (prev_v, curr_v) in visited_edge_directions and (prev_v, curr_v) != (u_start_node, v_start_node):
# print(f"Warning: Edge ({prev_v}, {curr_v}) visited again in face traversal.", file=sys.stderr)
break
# Mark this directed edge as visited.
visited_edge_directions.add((prev_v, curr_v))
# Store the edge (as sorted tuple) for path reconstruction/check.
path_edges.append(tuple(sorted((prev_v, curr_v))))
# Lookup the next vertex in CCW order using the precomputed map.
# Check if map entries exist to prevent KeyError.
if curr_v not in ccw_neighbor_map or prev_v not in ccw_neighbor_map[curr_v]:
# print(f"Error: Missing entry in ccw_neighbor_map for node {curr_v}, prev {prev_v}", file=sys.stderr)
break # Break if map lookup fails.
next_v = ccw_neighbor_map[curr_v][prev_v]
current_face_len += 1 # Increment face length.
# Update state for the next iteration.
prev_v = curr_v
curr_v = next_v
# Check termination condition: Have we returned to the starting edge?
# This means the current edge to traverse would be (u_start_node, v_start_node).
if prev_v == u_start_node and curr_v == v_start_node:
break # Completed the face cycle successfully.
# Safety break to prevent infinite loops if face length becomes excessively large.
if current_face_len > N + M + 5 : # Use a generous limit beyond |V|+|E|.
# print(f"Error: Face length limit exceeded", file=sys.stderr)
break
# After face traversal loop finishes: Check if it completed normally.
if prev_v == u_start_node and curr_v == v_start_node:
# Check if the discovered face is the unique outer face.
# The outer face has length N and its boundary consists solely of circle edges.
is_truly_outer_face = False
if current_face_len == N:
all_circle = True
for edge in path_edges:
p1, p2 = edge # edge is already sorted tuple (u, v) with u < v
# Check if it's a circle edge: form (p1, p1+1) or (1, N).
is_circle_edge_on_path = (p2 == p1 + 1) or (p1 == 1 and p2 == N)
if not is_circle_edge_on_path:
all_circle = False
break # Found a non-circle edge (wall) on boundary.
if all_circle:
is_truly_outer_face = True # It is the outer face.
# If it's not the outer face, it's an inner face. Update max inner face length.
if not is_truly_outer_face:
max_inner_face_len = max(max_inner_face_len, current_face_len)
# else: The loop terminated abnormally (e.g., error, safety break).
# We might ignore this face or log an error. Assume valid inputs lead to normal termination.
# Calculate K' = max(maximum vertex degree, maximum inner face length).
# This value represents the lower bound based on local constraints (degree/face size).
K_prime = max(max_degree, max_inner_face_len)
# The final result follows the hypothesis derived from analysis:
# The minimum number of colors required is max(K', 4).
# The value 4 comes from the fact that any edge requires at least 4 colors for its endpoints and incident faces.
# The special case N=3, M=0 requiring 5 colors is handled separately at the beginning.
print(max(K_prime, 4))
# Execute the solve function to process input and print the result.
solve()