結果

問題 No.1955 Not Prime
ユーザー srjywrdnprkt
提出日時 2025-03-16 02:30:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 3,546 bytes
コンパイル時間 4,681 ms
コンパイル使用メモリ 299,496 KB
実行使用メモリ 31,608 KB
最終ジャッジ日時 2025-03-16 02:30:11
合計ジャッジ時間 6,210 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<bool> prime_table;
void erat(ll N){
    prime_table.resize(N+1, 1);
    prime_table[0] = 0;
    prime_table[1] = 0;
    for (ll i=2; i*i<=N; i++){
        if (prime_table[i]){
            for (ll j=i*2; j <= N; j+=i){
                prime_table[j] = 0;
            }
        }
    }
}

vector<vector<int>> scc(const vector<vector<int>> &E){
    int N = E.size();
    
    vector<vector<int>> rev(N), components;
    vector<bool> vst(N);
    vector<int> order;

    for (int i=0; i<N; i++){
        for (auto x : E[i]) rev[x].push_back(i);
    }

    auto dfs1=[&](auto self, int from)->void{
        vst[from] = 1;
        for (int to : E[from]){
            if (vst[to]) continue;
            self(self, to);
        }
        order.push_back(from);
    };

    for (int i=0; i<N; i++) if (!vst[i]) dfs1(dfs1, i);

    reverse(order.begin(), order.end());
    fill(vst.begin(), vst.end(), 0);

    auto dfs2=[&](auto self, int from, vector<int> &comp)->void{
        vst[from] = 1;
        comp.push_back(from);
        for (int to : rev[from]){
            if (vst[to]) continue;
            self(self, to, comp);
        }
    };

    for (auto v : order){
        if (!vst[v]){
            vector<int> comp;
            dfs2(dfs2, v, comp);
            reverse(comp.begin(), comp.end());
            components.push_back(comp);
        }
    }

    return components;
}

//clause = [i1, i2, f1, f2]
// x_i1 = f1 or x_i2 = f2  (f1 = 0なら !x_i1)のような2個のリテラルからなる節の論理積がtrueとなる割り当て(x1, x2, ..., xN)を求める。存在しないなら空の配列を返す。
vector<bool> two_sat(int N, const vector<tuple<int, int, bool, bool>> &clause){

    vector<vector<int>> E(N*2), sc;
    for (auto [i1, i2, f1, f2] : clause){
        E[i1 * 2 + !f1].push_back(i2 * 2 + f2);
        E[i2 * 2 + !f2].push_back(i1 * 2 + f1);
    }
    sc = scc(E);
    int M = sc.size();
    vector<bool> res(N);
    vector<int> id(N*2);
    for (int i=0; i<M; i++){
        for (auto v : sc[i]) id[v] = i;
    }

    for (int i=0; i<N; i++){
        if (id[i*2] == id[i*2+1]) return {};
        res[i] = (id[i*2] < id[i*2+1]);
    }
    return res;
};

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

    /*
       x_i = 1 (iをSに振り分ける。)
       x_i = 0 (iをTに振り分ける。)

       A_i -> 2*i, B_i -> 2*i+1

       (1) z_{i*2} or z_{i*2+1} (どちらかがS)
       (2) !z_{i*2} or !z_{i*2+1} (どちらかがT)
       (3) if (prime(i*2, j*2+1)) !z_{i*2} or z_{j*2+1} = !(z_{i*2} and !z_{j*2+1}) (SとTが素数にならない)
    */

    erat(999999);
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    vector<tuple<int, int, bool, bool>> v;
    for (int i=0; i<N; i++) cin >> a[i] >> b[i];
    for (int i=0; i<N; i++){
        v.push_back({i*2, i*2+1, 1, 1});
        v.push_back({i*2, i*2+1, 0, 0});
    }

    auto f=[&](int x, int y)->bool{
        int res = stoi(to_string(x) + to_string(y));
        return prime_table[res];
    };

    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            if (f(a[i], a[j])) v.push_back({i*2, j*2, 0, 1});
            if (f(b[i], b[j])) v.push_back({i*2+1, j*2+1, 0, 1});
            if (f(a[i], b[j])) v.push_back({i*2, j*2+1, 0, 1});
            if (f(b[i], a[j])) v.push_back({i*2+1, j*2, 0, 1});
        }
    }

    vector<bool> ans = two_sat(N*2, v);
    cout << (ans.size() == 0 ? "No" : "Yes") << endl;

    return 0;
}
0