結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー rhoo
提出日時 2025-11-13 21:37:01
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 1,300 bytes
コンパイル時間 11,684 ms
コンパイル使用メモリ 400,248 KB
実行使用メモリ 34,088 KB
最終ジャッジ日時 2025-11-18 10:36:44
合計ジャッジ時間 12,881 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

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];
    let mut seen=vec![false;n];
    for &v in &que{
        seen[v]=true;
    }

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

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