結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー rhoo
提出日時 2025-11-13 21:34:41
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,154 bytes
コンパイル時間 13,127 ms
コンパイル使用メモリ 400,680 KB
実行使用メモリ 30,292 KB
最終ジャッジ日時 2025-11-13 21:34:58
合計ジャッジ時間 16,837 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*,mem::swap};
use proconio::{marker::*,*};



#[fastout]
fn main(){
    input!{
        n:usize,
        m:usize,
        es:[(Usize1,Usize1);m],
    }

    let mut g=vec![vec![];n];
    let mut rev=vec![vec![];n];
    let mut cnt=vec![0;n];

    for &(u,v) in &es{
        g[u].push(v);
        rev[v].push(u);
        cnt[u]+=1;
    }

    let mut que=(0..rev.len()).filter(|&v|cnt[v]==0).collect::<Vec<_>>();
    // 必敗:-1 必勝:1
    let mut dp=vec![0;n];

    while let Some(v)=que.pop(){
        if g[v].iter().all(|&pv|dp[pv]==1){
            dp[v]=-1;
            for &nv in &rev[v]{
                if dp[nv]==0{
                    que.push(nv);
                }
            }
        } else{
            dp[v]=1;
        }
        
        for &nv in &rev[v]{
            cnt[nv]-=1;
            if cnt[nv]==0 && dp[nv]==0{
                que.push(nv);
            }
        }
    }

    if dp[0]==1{
        println!("Alice");
    } else if dp[0]==-1{
        println!("Bob");
    } else{
        println!("Draw");
    }
}
0