結果
| 問題 |
No.1153 ねこちゃんゲーム
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:25:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,695 bytes |
| コンパイル時間 | 208 ms |
| コンパイル使用メモリ | 82,284 KB |
| 実行使用メモリ | 351,924 KB |
| 最終ジャッジ日時 | 2025-05-14 13:26:40 |
| 合計ジャッジ時間 | 10,273 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 5 TLE * 1 -- * 34 |
ソースコード
import sys
sys.setrecursionlimit(4 * 10**5)
# Global-like variables to store context for a single root's computation
_current_adj = None
_current_memo_for_root = None # Memoization for (curr, prev) states for the current root
_current_tin_for_root = None # tin values for DFS tree from the current root
_current_tout_for_root = None # tout values for DFS tree from the current root
_current_dfs_time_counter = 0 # Time counter for DFS
def dfs_tin_tout_builder(u, p):
global _current_dfs_time_counter, _current_tin_for_root, _current_tout_for_root, _current_adj
_current_dfs_time_counter += 1
_current_tin_for_root[u] = _current_dfs_time_counter
for v_neighbor in _current_adj[u]:
if v_neighbor == p:
continue
dfs_tin_tout_builder(v_neighbor, u)
_current_dfs_time_counter += 1
_current_tout_for_root[u] = _current_dfs_time_counter
def is_ancestor(u_potential_ancestor, v_node):
global _current_tin_for_root, _current_tout_for_root
# Check if u_potential_ancestor is an ancestor of v_node (or u_potential_ancestor == v_node)
# This check is valid only within the context of the current DFS tree (defined by _current_tin_for_root, _current_tout_for_root)
if u_potential_ancestor == 0: # Dummy node is not an ancestor of any real node
return False
if u_potential_ancestor not in _current_tin_for_root or v_node not in _current_tin_for_root:
# This might happen if nodes are not reachable from the current root (not an issue for a connected tree)
return False
return _current_tin_for_root[u_potential_ancestor] <= _current_tin_for_root[v_node] and \
_current_tout_for_root[u_potential_ancestor] >= _current_tout_for_root[v_node]
def calculate_grundy_for_state(curr_u, prev_p):
# fixed_root context is implicit via global _current_tin_for_root etc.
global _current_adj, _current_memo_for_root
state_key = (curr_u, prev_p)
if state_key in _current_memo_for_root:
return _current_memo_for_root[state_key]
reachable_next_states_grundies = set()
for neighbor_v in _current_adj[curr_u]:
if neighbor_v == prev_p: # Cannot immediately go back to where it came from
continue
# Check if neighbor_v is on the historical path from fixed_root to prev_p.
# The path taken so far is: fixed_root -> ... -> prev_p -> curr_u.
# The new node neighbor_v must not be in {fixed_root, ..., prev_p}.
# This is equivalent to: neighbor_v is not an ancestor of prev_p (inclusive) in the DFS tree from fixed_root.
# (prev_p == 0 is special: curr_u is fixed_root, history is just {fixed_root}.
# neighbor_v is forbidden only if neighbor_v == fixed_root, but neighbor_v != curr_u.)
is_forbidden_by_history = False
if prev_p != 0: # If prev_p is not the dummy node
if is_ancestor(neighbor_v, prev_p):
is_forbidden_by_history = True
if not is_forbidden_by_history:
reachable_next_states_grundies.add(calculate_grundy_for_state(neighbor_v, curr_u))
g_val = 0
while g_val in reachable_next_states_grundies:
g_val += 1
_current_memo_for_root[state_key] = g_val
return g_val
def solve():
global _current_adj, _current_memo_for_root, _current_tin_for_root, _current_tout_for_root, _current_dfs_time_counter
N, M = map(int, sys.stdin.readline().split())
# A_starts contains the 1-indexed starting nodes for cats 0 to M-1
A_starts = list(map(int, sys.stdin.readline().split()))
_current_adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
u, v_node = map(int, sys.stdin.readline().split())
_current_adj[u].append(v_node)
_current_adj[v_node].append(u)
if N == 1: # Single node tree
print("-1 -1") # No moves possible
return
# Store computed Grundy values for G(start_node, dummy_prev_node)
# Key: start_node, Value: Grundy value
# Also cache tin/tout maps to avoid recomputing DFS if same root is processed again.
grundy_values_for_each_distinct_start_node = {}
tin_maps_cache = {}
tout_maps_cache = {}
distinct_start_nodes = sorted(list(set(A_starts)))
for s_node in distinct_start_nodes:
_current_dfs_time_counter = 0
_current_tin_for_root = {}
_current_tout_for_root = {}
_current_memo_for_root = {} # Fresh memo for this root
dfs_tin_tout_builder(s_node, 0) # 0 is a dummy parent for the root s_node
# Cache tin/tout for potential reuse when finding the winning move
tin_maps_cache[s_node] = dict(_current_tin_for_root)
tout_maps_cache[s_node] = dict(_current_tout_for_root)
# Calculate Grundy value for starting at s_node (previous node is dummy 0)
g_val = calculate_grundy_for_state(s_node, 0)
grundy_values_for_each_distinct_start_node[s_node] = g_val
# Calculate XOR sum of all cats' initial Grundy values
total_grundy_xor_sum = 0
# cat_initial_grundies[i] stores G-value for i-th cat (0-indexed)
cat_initial_grundies = [0] * M
for i in range(M):
cat_i_start_node = A_starts[i]
g_val = grundy_values_for_each_distinct_start_node[cat_i_start_node]
cat_initial_grundies[i] = g_val
total_grundy_xor_sum ^= g_val
if total_grundy_xor_sum == 0:
print("-1 -1") # Kiri-chan wins
else:
# Ebi-chan wins. Find a winning move.
# Iterate through each cat. If moving cat k makes its Grundy value G_k',
# then we need G_k' == total_grundy_xor_sum ^ G_k_initial.
found_winning_move = False
for cat_list_idx in range(M): # cat_list_idx is 0 to M-1
cat_actual_id = cat_list_idx + 1 # Problem uses 1-indexed cat IDs
current_cat_origin_node = A_starts[cat_list_idx]
current_cat_initial_g_val = cat_initial_grundies[cat_list_idx]
target_g_val_for_next_state = total_grundy_xor_sum ^ current_cat_initial_g_val
# Set up context for this cat's origin_node
_current_tin_for_root = tin_maps_cache[current_cat_origin_node]
_current_tout_for_root = tout_maps_cache[current_cat_origin_node]
_current_memo_for_root = {} # Fresh memo for this calculation phase, or could reuse if states are truly identical
# Iterate over possible first moves for this cat
# Current state for this cat: (current_cat_origin_node, dummy_prev_0)
# A move is to neighbor_v.
# The state after move: (neighbor_v, current_cat_origin_node as prev_p)
for neighbor_v_of_origin in _current_adj[current_cat_origin_node]:
# The history for this move is {current_cat_origin_node, neighbor_v_of_origin}.
# The call is calculate_grundy_for_state(neighbor_v_of_origin, current_cat_origin_node)
# fixed_root for this game is current_cat_origin_node.
g_val_of_state_after_move = calculate_grundy_for_state(neighbor_v_of_origin, current_cat_origin_node)
if g_val_of_state_after_move == target_g_val_for_next_state:
print(f"{cat_actual_id} {neighbor_v_of_origin}")
found_winning_move = True
break
if found_winning_move:
break
# According to Sprague-Grundy theorem, a winning move must exist.
# If not found, it indicates a bug in implementation or understanding.
# assert found_winning_move
solve()