結果

問題 No.3340 Simple Graph Game
コンテスト
ユーザー りすりす/TwoSquirrels
提出日時 2025-11-11 09:24:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,884 bytes
コンパイル時間 1,415 ms
コンパイル使用メモリ 128,864 KB
実行使用メモリ 36,624 KB
最終ジャッジ日時 2025-11-13 21:17:41
合計ジャッジ時間 7,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Gemini 2.5 Pro に嘘ヒントを教えて出力された嘘解法

#include <iostream>
#include <vector>
#include <string>
#include <set> // 縮約グラフの重複辺除去
#include <atcoder/scc> // ACLのSCCライブラリ

using namespace std;
using namespace atcoder;

// 勝敗の状態 (0: LOSE, 1: WIN, 2: DRAW)
enum GameResult { LOSE = 0, WIN = 1, DRAW = 2 };

int main() {
    int N, M;
    cin >> N >> M;

    scc_graph graph(N);
    vector<pair<int, int>> edges; // 元の辺リスト (0-indexed)
    vector<bool> has_self_loop(N, false); // 自己ループ判定用

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        u--; // 0-indexed に
        v--; 
        graph.add_edge(u, v);
        edges.push_back({u, v});
        if (u == v) {
            has_self_loop[u] = true;
        }
    }

    // --- 1. SCC ---
    vector<vector<int>> sccs = graph.scc();
    int num_scc = sccs.size();

    // scc_id[v] = 頂点vが属するSCCのID
    vector<int> scc_id(N);
    for (int i = 0; i < num_scc; ++i) {
        for (int v : sccs[i]) {
            scc_id[v] = i;
        }
    }

    // --- 2. サイクル判定 (DRAWの可能性) ---
    // scc_is_draw[i] = SCC i がサイクル(DRAW)可能か
    vector<bool> scc_is_draw(num_scc, false);
    for (int i = 0; i < num_scc; ++i) {
        if (sccs[i].size() >= 2) {
            // 頂点数が2以上ならサイクル
            scc_is_draw[i] = true;
        } else {
            // 頂点数が1の場合、自己ループがあるか
            int u = sccs[i][0];
            if (has_self_loop[u]) {
                scc_is_draw[i] = true;
            }
        }
    }

    // --- 3. 縮約グラフ構築 ---
    // scc_adj[i] = SCC i から到達可能なSCCのIDリスト (重複なし)
    vector<set<int>> scc_adj(num_scc);
    for (const auto& edge : edges) {
        int u_id = scc_id[edge.first];
        int v_id = scc_id[edge.second];
        if (u_id != v_id) {
            scc_adj[u_id].insert(v_id);
        }
    }

    // --- 4. 後退解析 (DP) ---
    // dp[i] = SCC i からゲームを始めたときの勝敗
    vector<GameResult> dp(num_scc);

    // ACLのSCCはトポロジカルソート順なので、IDの大きい方(末端)から処理
    for (int i = num_scc - 1; i >= 0; --i) {
        
        // デフォルトは LOSE (遷移先がすべて WIN か、遷移先なし)
        dp[i] = LOSE; 
        
        bool can_move_to_draw = false;
        
        // 遷移先をチェック
        for (int next_scc_id : scc_adj[i]) {
            if (dp[next_scc_id] == LOSE) {
                // 優先度1: 相手をLOSEにできるなら、自分はWIN
                dp[i] = WIN;
                break; // このSCCの判定終了
            }
            if (dp[next_scc_id] == DRAW) {
                can_move_to_draw = true;
            }
        }

        // (もし dp[i] == WIN なら、この continue が実行される)
        if (dp[i] == WIN) continue; 

        // (LOSEには行けなかった場合)
        
        if (scc_is_draw[i]) {
            // 優先度2: 自分がサイクル持ち (DRAW可能)
            dp[i] = DRAW;
        } else if (can_move_to_draw) {
            // 優先度3: 自分がサイクル持ちでないが、DRAW には行ける
            dp[i] = DRAW;
        }
        
        // 優先度4: (dp[i] == LOSE のまま)
        // LOSEに行けず、自分もサイクルでなく、DRAWにも行けない
        // = 遷移先はすべてWIN、または遷移先なし
    }

    // --- 5. 判定 ---
    int start_scc_id = scc_id[0]; // スタート(頂点1 -> 0)

    if (dp[start_scc_id] == WIN) {
        cout << "Alice" << endl;
    } else if (dp[start_scc_id] == LOSE) {
        cout << "Bob" << endl;
    } else { // DRAW
        cout << "Draw" << endl;
    }

    return 0;
}
0