結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー norioc
提出日時 2025-11-19 22:11:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 605 ms / 2,000 ms
コード長 1,190 bytes
コンパイル時間 2,179 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 156,968 KB
最終ジャッジ日時 2025-11-19 22:11:22
合計ジャッジ時間 16,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque, defaultdict

WIN = 0
LOSE = 1
DRAW = 2


def detect_graph_game(n: int, adj: dict[int, list[int]]) -> list[int]:
    res = [DRAW] * n
    r_adj = defaultdict(list)
    refs = [0] * n
    q = deque()
    for i in range(n):
        nexts = adj[i]
        for to in nexts:
            r_adj[to].append(i)

        refs[i] = len(nexts)
        if len(nexts) == 0:
            res[i] = LOSE  # 遷移できないなら負け
            q.append(i)

    while q:
        v = q.popleft()

        for prev in r_adj[v]:  # 遷移元
            if res[prev] == WIN: continue

            if res[v] == LOSE:  # 負けで遷移できるなら勝ち
                res[prev] = WIN
                q.append(prev)
            else:
                refs[prev] -= 1
                if refs[prev] == 0:
                    res[prev] = LOSE
                    q.append(prev)

    return res


N, M = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    U, V = map(lambda x: int(x)-1, input().split())
    adj[U].append(V)

res = detect_graph_game(N, adj)
if res[0] == WIN:
    print('Alice')
elif res[0] == LOSE:
    print('Bob')
else:
    print('Draw')
0