結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー haru018
提出日時 2025-11-14 00:31:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,023 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 111,984 KB
最終ジャッジ日時 2025-11-14 00:32:08
合計ジャッジ時間 13,816 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(n)]
ginv = [[] for _ in range(n)]
for _ in range(m):
    _u, _v = map(lambda x: int(x) - 1, input().split())
    g[_u].append(_v)
    ginv[_v].append(_u)

det = [0] * n
Q = deque([])
for v, l in enumerate(g):
    if not l:
        det[v] = -1
        for u in ginv[v]:
            Q.append(u)

if not Q:
    print("Draw")
    quit()
if det[0] == -1:
    print("Bob")
    quit()

while Q:
    v = Q.popleft()
    if det[v] == 1:
        continue
    det[v] = 1
    if v == 0:
        print("Alice")
        quit()
    for u in ginv[v]:
        if det[u] == 0:
            for w in g[u]:
                if det[w] != 1:
                    break
            else:
                det[u] = -1
                if u == 0:
                    print("Bob")
                    quit()
                for w in g[u]:
                    Q.append(w)

if det[0] == 1:
    print("Alice")
elif det[0] == -1:
    print("Bob")
else:
    print("Draw")
0