結果

問題 No.1153 ねこちゃんゲーム
ユーザー qwewe
提出日時 2025-05-14 13:24:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,913 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 848,836 KB
最終ジャッジ日時 2025-05-14 13:26:08
合計ジャッジ時間 15,875 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 MLE * 5 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Increase recursion limit for deep recursive calls on paths
sys.setrecursionlimit(4 * 10**5) 

memo = {}  # Memoization table for Grundy values
adj = []   # Adjacency list for the tree

def compute_grundy(u, visited_fset):
    """
    Calculates the Grundy value for a cat.
    u: current vertex of the cat (1-indexed)
    visited_fset: frozenset of vertices visited by this cat so far (includes u)
    """
    state = (u, visited_fset)
    if state in memo:
        return memo[state]

    seen_grundy_values_of_options = set()
    # adj is 0-indexed, u is 1-indexed
    for neighbor_node in adj[u - 1]: 
        if neighbor_node not in visited_fset:
            # Move cat to neighbor_node
            # New visited set includes the neighbor_node
            new_visited_fset = visited_fset.union({neighbor_node})
            seen_grundy_values_of_options.add(compute_grundy(neighbor_node, new_visited_fset))
    
    # Calculate mex of the set of Grundy values of options
    g = 0
    while g in seen_grundy_values_of_options:
        g += 1
    
    memo[state] = g
    return g

def solve():
    global adj # Allow modification of global adj
    N, M = map(int, sys.stdin.readline().split())
    initial_cat_positions = list(map(int, sys.stdin.readline().split()))

    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        u_edge, v_edge = map(int, sys.stdin.readline().split())
        adj[u_edge - 1].append(v_edge)
        adj[v_edge - 1].append(u_edge)

    # Handle N=1 case: No moves possible
    if N == 1:
        print("-1 -1")
        return

    cat_initial_grundy_values = []
    for i in range(M):
        cat_start_node = initial_cat_positions[i]
        initial_visited_fset = frozenset({cat_start_node})
        val = compute_grundy(cat_start_node, initial_visited_fset)
        cat_initial_grundy_values.append(val)

    nim_sum = 0
    for g_val in cat_initial_grundy_values:
        nim_sum ^= g_val

    if nim_sum == 0:
        # QiQi (second player) wins
        print("-1 -1")
    else:
        # XiaXia (first player) wins, find an optimal move
        for i in range(M):  # Iterate through each cat
            cat_id_1_indexed = i + 1
            current_pos = initial_cat_positions[i]
            
            # Grundy value of the game if this cat i was removed (or its subgame's G was 0)
            # is nim_sum XOR cat_initial_grundy_values[i]
            # We want the new Grundy value of cat i's subgame (g_prime_k) to be this value.
            target_grundy_for_cat_after_move = nim_sum ^ cat_initial_grundy_values[i]
            
            initial_visited_fset_for_this_cat = frozenset({current_pos})

            # Iterate over possible moves for this cat
            # adj is 0-indexed, current_pos is 1-indexed
            for neighbor_node in adj[current_pos - 1]:
                # A move to neighbor_node is valid if neighbor_node is not in initial_visited_fset_for_this_cat.
                # Since initial_visited_fset_for_this_cat only contains current_pos, any neighbor is valid for the first move (as long as N > 1).
                
                # Calculate Grundy value of cat i's subgame AFTER moving to neighbor_node
                visited_fset_after_move = initial_visited_fset_for_this_cat.union({neighbor_node})
                grundy_of_cat_after_move = compute_grundy(neighbor_node, visited_fset_after_move)
                
                if grundy_of_cat_after_move == target_grundy_for_cat_after_move:
                    print(f"{cat_id_1_indexed} {neighbor_node}")
                    return
        
        # According to Sprague-Grundy theorem, if nim_sum != 0, a winning move must exist.
        # If code reaches here, it implies an issue (e.g. a cat had no valid first moves but N > 1, 
        # or a logical error in applying the theorem). For this problem structure, a move should always be found.

solve()
0