結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー 2251799813685248
提出日時 2025-11-14 01:49:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 189 ms / 2,000 ms
コード長 3,007 bytes
コンパイル時間 1,080 ms
コンパイル使用メモリ 127,108 KB
実行使用メモリ 26,664 KB
最終ジャッジ日時 2025-11-18 10:40:10
合計ジャッジ時間 5,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>


using namespace std;
#define ll long long
#define MOD 998244353
#define ld long double
#define INF 2251799813685248
#define vall(A) A.begin(),A.end()
#define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}}
#define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}}
#define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}
#define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}
#define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}}
#define encode(i,j) ((i)<<32)+j
#define decode(v,w) (w ? (v)%4294967296 : (v)>>32)
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};

int main(){
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> E(N+1);
    vector<vector<ll>> F(N+1);//入ってくる辺
    vector<ll> state(N+1,-1);//-1未確定。0負け。1勝ち
    vector<ll> access_by_win_vertex(N+1,0);
    deque<ll> Q;
    for (ll i = 0; i < M; i++){
        ll u,v;
        cin >> u >> v;
        E[u].push_back(v);
        F[v].push_back(u);
    }
    for (ll i = 1; i <= N; i++){
        if (E[i].size() == 0){
            Q.push_back(i);
            state[i] = 0;
        }
    }

    while (!Q.empty()){
        ll now = Q.front();
        Q.pop_front();
        if (state[now] == 0){
            for (auto v : F[now]){
                if (state[v] != -1){continue;}
                state[v] = 1;
                Q.push_back(v);
            }
        }
        else{
            for (auto v : F[now]){
                if (state[v] != -1){continue;}
                access_by_win_vertex[v]++;
                if (access_by_win_vertex[v] == E[v].size()){
                    state[v] = 0;
                    Q.push_back(v);
                }
            }
        }
    }

    if (state[1] == 0){
        cout << "Bob";
    }
    else if (state[1] == -1){
        cout << "Draw";
    }
    else if (state[1] == 1){
        cout << "Alice";
    }
    cout << endl;

}
0