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

• 問題: No.3508 OR Mapping
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 06:02:22
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 438 ms / 2,000 ms
• コード長: 5,105 bytes
• コンパイル時間: 3,079 ms
• コンパイル使用メモリ: 363,512 KB
• 実行使用メモリ: 142,152 KB
• 最終ジャッジ日時: 2026-04-18 06:02:42
• 合計ジャッジ時間: 19,584 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

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

using ll = long long;

static ll gcd2(ll a, ll b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

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

    int n, m;
    ll k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n), rev(n);
    vector<pair<int,int>> edges;
    edges.reserve(m);

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

        adj[u].push_back(v);
        rev[v].push_back(u);
        edges.push_back({u, v});
    }

    vector<int> vis(n, 0), ord;
    ord.reserve(n);

    for (int s = 0; s < n; s++) {
        if (vis[s]) continue;

        vector<pair<int,int>> st;
        st.push_back({s, 0});
        vis[s] = 1;

        while (!st.empty()) {
            int v = st.back().first;
            int &idx = st.back().second;

            if (idx < (int)adj[v].size()) {
                int to = adj[v][idx++];
                if (!vis[to]) {
                    vis[to] = 1;
                    st.push_back({to, 0});
                }
            } else {
                ord.push_back(v);
                st.pop_back();
            }
        }
    }

    vector<int> comp(n, -1);
    vector<vector<int>> groups;

    for (int i = n - 1; i >= 0; i--) {
        int s = ord[i];
        if (comp[s] != -1) continue;

        int id = (int)groups.size();
        groups.push_back({});

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

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            groups[id].push_back(v);

            for (int to : rev[v]) {
                if (comp[to] == -1) {
                    comp[to] = id;
                    st.push_back(to);
                }
            }
        }
    }

    int cnt = (int)groups.size();
    int start = comp[0];

    vector<pair<int,int>> dagEdges;
    dagEdges.reserve(m);

    for (auto &e : edges) {
        int a = comp[e.first];
        int b = comp[e.second];
        if (a != b) dagEdges.push_back({a, b});
    }

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

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

    for (auto &e : dagEdges) {
        dag[e.first].push_back(e.second);
        indeg[e.second]++;
    }

    vector<int> can(cnt, 0);
    {
        vector<int> st = {start};
        can[start] = 1;

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();

            for (int to : dag[v]) {
                if (!can[to]) {
                    can[to] = 1;
                    st.push_back(to);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (!can[comp[i]]) {
            cout << "No\n";
            return 0;
        }
    }

    vector<int> indeg2 = indeg;
    queue<int> q2;
    for (int i = 0; i < cnt; i++) {
        if (indeg2[i] == 0) q2.push(i);
    }

    vector<int> topo;
    topo.reserve(cnt);

    while (!q2.empty()) {
        int v = q2.front();
        q2.pop();
        topo.push_back(v);

        for (int to : dag[v]) {
            indeg2[to]--;
            if (indeg2[to] == 0) q2.push(to);
        }
    }

    vector<ll> dist(n, -1);
    vector<int> good(cnt, 0), one(cnt, 0);

    for (int id = 0; id < cnt; id++) {
        if (!can[id]) continue;

        if ((int)groups[id].size() == 1) {
            one[id] = 1;
            continue;
        }

        ll g = 0;
        int root = groups[id][0];

        for (int v : groups[id]) dist[v] = -1;

        vector<int> st = {root};
        dist[root] = 0;

        while (!st.empty()) {
            int v = st.back();
            st.pop_back();

            for (int to : adj[v]) {
                if (comp[to] != id) continue;

                if (dist[to] == -1) {
                    dist[to] = dist[v] + 1;
                    st.push_back(to);
                } else {
                    g = gcd2(g, dist[v] + 1 - dist[to]);
                }
            }
        }

        g = llabs(g);
        if (g % 2 == 1) good[id] = 1;
    }

    if (!good[start]) {
        cout << "No\n";
        return 0;
    }

    for (int id = 0; id < cnt; id++) {
        if (!can[id]) continue;

        if (!good[id] && !one[id]) {
            cout << "No\n";
            return 0;
        }
    }

    const int NEG = -1000000000;
    vector<int> dp(cnt, NEG);
    dp[start] = 1;

    int need = 0;
    for (int i = 0; i < cnt; i++) {
        if (can[i]) need++;
    }

    for (int v : topo) {
        if (!can[v]) continue;
        if (dp[v] < 0) continue;

        for (int to : dag[v]) {
            if (!can[to]) continue;
            if (one[v] && one[to]) continue;

            dp[to] = max(dp[to], dp[v] + 1);
        }
    }

    int best = 0;
    for (int i = 0; i < cnt; i++) {
        if (can[i]) best = max(best, dp[i]);
    }

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