#1160264 (C++23) No.3508 OR Mapping

• 問題: No.3508 OR Mapping
• ユーザー: sient
• 提出日時: 2026-04-19 01:01:43
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 294 ms / 2,000 ms
• コード長: 3,855 bytes
• コンパイル時間: 3,864 ms
• コンパイル使用メモリ: 355,236 KB
• 実行使用メモリ: 68,872 KB
• 最終ジャッジ日時: 2026-04-19 01:02:33
• 合計ジャッジ時間: 16,794 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
sample	AC * 2
other	AC * 65

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct EdgeGraph {
    int n;
    vector<int> head, to, nxt;
    int ecnt = 0;

    EdgeGraph(int n, int m) : n(n), head(n, -1), to(m), nxt(m) {}

    void add_edge(int u, int v) {
        to[ecnt] = v;
        nxt[ecnt] = head[u];
        head[u] = ecnt++;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    int V = 2 * N;
    EdgeGraph g(V, 2 * M), rg(V, 2 * M);

    auto id = [&](int v, int p) {
        return 2 * v + p;
    };

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;

        g.add_edge(id(u, 0), id(v, 1));
        g.add_edge(id(u, 1), id(v, 0));

        rg.add_edge(id(v, 1), id(u, 0));
        rg.add_edge(id(v, 0), id(u, 1));
    }

    int start = id(0, 0);

    vector<char> reach(V, 0);
    vector<int> order;
    order.reserve(V);

    {
        vector<int> st;
        vector<int> it(V, -1);

        reach[start] = 1;
        st.push_back(start);
        it[start] = g.head[start];

        while (!st.empty()) {
            int v = st.back();
            int &e = it[v];

            while (e != -1 && reach[g.to[e]]) e = g.nxt[e];

            if (e != -1) {
                int u = g.to[e];
                e = g.nxt[e];
                reach[u] = 1;
                st.push_back(u);
                it[u] = g.head[u];
            } else {
                order.push_back(v);
                st.pop_back();
            }
        }
    }

    vector<int> comp(V, -1);
    int C = 0;

    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int s = order[i];
        if (comp[s] != -1) continue;

        vector<int> st = {s};
        comp[s] = C;

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            for (int e = rg.head[v]; e != -1; e = rg.nxt[e]) {
                int u = rg.to[e];
                if (reach[u] && comp[u] == -1) {
                    comp[u] = C;
                    st.push_back(u);
                }
            }
        }
        ++C;
    }

    vector<pair<int,int>> dag_edges;
    dag_edges.reserve(2 * M);

    for (int v = 0; v < V; ++v) {
        if (!reach[v]) continue;
        for (int e = g.head[v]; e != -1; e = g.nxt[e]) {
            int u = g.to[e];
            if (!reach[u]) continue;
            if (comp[v] != comp[u]) {
                dag_edges.push_back({comp[v], comp[u]});
            }
        }
    }

    sort(dag_edges.begin(), dag_edges.end());
    dag_edges.erase(unique(dag_edges.begin(), dag_edges.end()), dag_edges.end());

    vector<vector<int>> dag(C);
    vector<int> indeg(C, 0);

    for (auto [a, b] : dag_edges) {
        dag[a].push_back(b);
        ++indeg[b];
    }

    vector<int> need(C, 0);
    int total_need = 0;

    for (int v = 0; v < N; ++v) {
        int t = id(v, 1);
        if (!reach[t]) {
            cout << "No\n";
            return 0;
        }
        int c = comp[t];
        if (!need[c]) {
            need[c] = 1;
            ++total_need;
        }
    }

    queue<int> q;
    for (int i = 0; i < C; ++i) {
        if (indeg[i] == 0) q.push(i);
    }

    vector<int> topo;
    topo.reserve(C);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (int u : dag[v]) {
            if (--indeg[u] == 0) q.push(u);
        }
    }

    const int NEG = -1e9;
    vector<int> dp(C, NEG);
    int start_comp = comp[start];
    dp[start_comp] = need[start_comp];

    for (int v : topo) {
        if (dp[v] == NEG) continue;
        for (int u : dag[v]) {
            dp[u] = max(dp[u], dp[v] + need[u]);
        }
    }

    int best = 0;
    for (int x : dp) best = max(best, x);

    cout << (best == total_need ? "Yes\n" : "No\n");
    return 0;
}