結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー hato336
提出日時 2025-11-13 21:26:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,991 bytes
コンパイル時間 2,871 ms
コンパイル使用メモリ 286,688 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-18 10:35:53
合計ジャッジ時間 6,183 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;

#define i128 __int128_t

int main() { 
    cin.tie(0)->sync_with_stdio(0);
    ll n,m;
    cin >> n >> m;
    vector<vi> edge(n);
    vector<vi> edge2(n);
    rep(i,m){
        ll u,v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge2[v].push_back(u);
    }
    vl a(n,-1);
    queue<ll> q;
    rep(i,n){
        if(edge[i].size() == 0){
            q.emplace(i);
        }
    }
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        if(edge[x].size() == 0){
            a[x] = 0;
        }
        ll cnt = 0;
        for(auto to:edge[x]){
            if(a[to] == 0){
                a[x] = 1;
            }
            if(a[to] == 1){
                cnt++;
            }
        }
        if(cnt == edge[x].size()){
            a[x] = 0;
        }
        if(a[x] == -1){continue;}
        for(auto to:edge2[x]){
            if(a[to] == -1){
                q.emplace(to);
            }
        }
    }
    cerr << a[0] << endl;
    cout << (a[0] == 1 ? "Alice" : a[0] == 0 ? "Bob" : "Draw") << endl;
}
0