結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー jupiter_68
提出日時 2025-10-29 18:06:06
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 2,664 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,573 ms
コンパイル使用メモリ 289,836 KB
実行使用メモリ 24,216 KB
最終ジャッジ日時 2025-11-18 10:34:57
合計ジャッジ時間 5,896 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

void solve(){
    ll N, M; cin >> N >> M;
    vv<ll> G(N), rG(N);
    vl d(N);
    rep(i, M){
        ll u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        rG[v].push_back(u);
        d[u]++;
    }
    queue<ll> Q;
    vl dp(N, -1);
    vec<bool> vis(N, 0);
    rep(i, N){
        if(!d[i]){
            Q.push(i);
            dp[i] = 0;
            vis[i] = 1;
        }
    }
    while(!Q.empty()){
        ll p = Q.front(); Q.pop();
        if(dp[p] == 1){
            for(ll nx : rG[p]){
                if(vis[nx]) continue;
                d[nx]--;
                if(!d[nx]){
                    Q.push(nx);
                    vis[nx] = 1;
                }
            }
            continue;
        }
        else{
            dp[p] = 0;
            for(ll nx : rG[p]){
                dp[nx] = 1;
                if(!vis[nx]){
                    Q.push(nx);
                    vis[nx] = 1;
                }
            }
            continue;
        }
    }
    if(dp[0] == 1){
        cout << "Alice" << endl;
        return;
    }
    if(dp[0] == 0){
        cout << "Bob" << endl;
        return;
    }
    cout << "Draw" << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
0