結果

問題 No.3508 OR Mapping
コンテスト
ユーザー takuma saito
提出日時 2026-04-18 23:36:02
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,687 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,690 ms
コンパイル使用メモリ 346,688 KB
実行使用メモリ 138,432 KB
最終ジャッジ日時 2026-04-18 23:37:51
合計ジャッジ時間 17,802 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 50 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

typedef long long ll;

struct SCC {
    int n;
    vector<vector<int>> g, rg;
    vector<int> vs, cmp;
    vector<bool> used;
    SCC(int n) : n(n), g(n), rg(n), cmp(n), used(n) {}
    void add_edge(int from, int to) {
        g[from].push_back(to);
        rg[to].push_back(from);
    }
    void dfs(int v) {
        used[v] = true;
        for (int next : g[v]) if (!used[next]) dfs(next);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (int next : rg[v]) if (!used[next]) rdfs(next, k);
    }
    int sol() {
        fill(used.begin(), used.end(), false);
        for (int v = 0; v < n; v++) if (!used[v]) dfs(v);
        fill(used.begin(), used.end(), false);
        int k = 0;
        reverse(vs.begin(), vs.end());
        for (int v : vs) if (!used[v]) rdfs(v, k++);
        return k;
    }
};

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K;
    cin >> N >> M >> K;

    SCC scc(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        scc.add_edge(u, v);
    }

    int num = scc.sol();
    vector<vector<int>> X(num);
    for (int i = 0; i < N; i++) X[scc.cmp[i]].push_back(i);
//ok
    vector<bool> ok(N, false);
    vector<int> q;
    ok[0] = true;
    q.push_back(0);
    for(int i=0; i<(int)q.size(); ++i){
        for(int next : scc.g[q[i]]) if(!ok[next]){
            ok[next] = true;
            q.push_back(next);
        }
    }
//しゅうき
    vector<ll> dist(N, -1);
    vector<ll> A(num, 0); 
    for (int i = 0; i < num; i++) {
        if (X[i].empty()) continue;
        int root = X[i][0];
        dist[root] = 0;
        vector<int> st = {root};
        int top = 0;
        while(top < (int)st.size()){
            int v = st[top++];
            for(int next : scc.g[v]){
                if(scc.cmp[next] != i) continue; 
                if(dist[next] == -1){
                    dist[next] = dist[v] + 1;
                    st.push_back(next);
                } else {
                    ll d = abs(dist[next] - (dist[v] + 1));
                    A[i] = gcd(A[i], d);
                }
            }
        }
    }

    vector<bool> ok2(num, false);
    for (int i = 0; i < num; i++) {
        if (A[i] > 0 && A[i] % 2 != 0) {
            ok2[i] = true;
        }
    }

    for (int i = 0; i < N; i++) {
        if (ok[i]) {
            if (!ok2[scc.cmp[i]]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}
0