結果

問題 No.1153 ねこちゃんゲーム
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:05:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,539 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 293,160 KB
最終ジャッジ日時 2025-04-09 21:07:48
合計ジャッジ時間 52,562 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 26 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+M]))
    ptr += M
    adj = [[] for _ in range(N+1)]  # 1-based
    for _ in range(N-1):
        u, v = int(input[ptr]), int(input[ptr+1])
        adj[u].append(v)
        adj[v].append(u)
        ptr += 2
    
    # Compute grundy numbers for required (v, p) pairs
    memo = dict()  # (v, p) => grundy number
    visited = set()
    stack = []
    
    # Collect all required (u, a) pairs where a is a cat's position and u is adjacent to a
    required = set()
    for a in A:
        for u in adj[a]:
            required.add( (u, a) )
    
    # Add all required (u, a) pairs to the stack if not processed
    for (v, p) in required:
        if (v, p) not in visited:
            stack.append( (v, p, False) )
            visited.add( (v, p) )
    
    # Process the stack to compute grundy numbers
    while stack:
        v, p, processed = stack.pop()
        if not processed:
            if (v, p) in memo:
                continue
            # Push back with processed=True
            stack.append( (v, p, True) )
            # Push all children (u != p)
            for u in adj[v]:
                if u != p:
                    if (u, v) not in memo and (u, v) not in visited:
                        stack.append( (u, v, False) )
                        visited.add( (u, v) )
        else:
            s = set()
            for u in adj[v]:
                if u != p:
                    s.add( memo.get( (u, v), 0 ) )
            mex = 0
            while mex in s:
                mex += 1
            memo[(v, p)] = mex
    
    # Compute initial grundy numbers for each cat
    g_total = 0
    g_list = []
    for a in A:
        neighbors = adj[a]
        s = set()
        for u in neighbors:
            s.add( memo.get( (u, a), 0 ) )
        mex = 0
        while mex in s:
            mex += 1
        g_list.append(mex)
        g_total ^= mex
    
    if g_total == 0:
        print("-1 -1")
        return
    
    # Find the first possible move
    for idx in range(M):
        a = A[idx]
        target = g_total ^ g_list[idx]
        for u in adj[a]:
            if memo.get( (u, a), 0 ) == target:
                print(idx+1, u)
                return
    
    # Should not reach here if grundy theory is correct
    print("-1 -1")

if __name__ == '__main__':
    main()
0