結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー Koi
提出日時 2025-11-13 21:31:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 998 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 115,756 KB
最終ジャッジ日時 2025-11-13 21:31:38
合計ジャッジ時間 13,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
Graph = [[] for _ in range(N)]
RevG = [[] for _ in range(N)]
Outs = [0] * N
for i in range(M):
    u, v = map(int, input().split())
    Graph[u - 1].append(v - 1)
    RevG[v - 1].append(u - 1)
    Outs[u - 1] += 1
L = []
Result = [-1] * N
#Result[i]:=頂点iに駒がある状態でゲームをした時、0なら先手が勝つ1なら後手が勝つ-1なら引き分け
for i in range(N):
    if(Outs[i] == 0):
        L.append(i)
        Result[i] = 1
while len(L):
    p = L.pop()
    #Result[p]を決める
    Sub = set()
    for nxt in Graph[p]:
        Sub.add(Result[nxt])
    if(1 in Sub):
        Result[p] = 0
    elif(-1 in Sub):
        Result[p] = -1
    else:
        Result[p] = 1
    for pre in RevG[p]:
        Outs[pre] -= 1
        if(Outs[pre] == 0):
            L.append(pre)
# ほんとう？
Sub = set()
for nxt in Graph[0]:
    Sub.add(Result[nxt])
if(1 in Sub):
    print("Alice")
elif(-1 in Sub):
    print("Draw")
else:
    print("Bob")
0