#765118 (C++17) No.1955 Not Prime

提出ソース

結果

問題	No.1955 Not Prime
ユーザー	raven7959
提出日時	2022-05-22 16:33:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,851 bytes
コンパイル時間	2,802 ms
コンパイル使用メモリ	228,288 KB
実行使用メモリ	115,776 KB
最終ジャッジ日時	2024-09-20 12:42:04
合計ジャッジ時間	4,559 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	22 ms 11,548 KB
testcase_01	AC	22 ms 11,552 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	23 ms 11,428 KB
testcase_06	AC	26 ms 12,204 KB
testcase_07	AC	64 ms 18,240 KB
testcase_08	AC	53 ms 17,340 KB
testcase_09	AC	75 ms 17,344 KB
testcase_10	AC	66 ms 11,712 KB
testcase_11	AC	162 ms 115,776 KB
testcase_12	AC	37 ms 14,004 KB
testcase_13	AC	78 ms 19,652 KB
testcase_14	AC	31 ms 13,868 KB
testcase_15	AC	31 ms 13,748 KB
testcase_16	AC	46 ms 16,824 KB
testcase_17	AC	67 ms 19,908 KB
testcase_18	AC	77 ms 19,008 KB
testcase_19	AC	84 ms 25,412 KB
testcase_20	AC	23 ms 11,552 KB
testcase_21	AC	39 ms 14,264 KB
testcase_22	AC	22 ms 11,552 KB
testcase_23	AC	21 ms 11,680 KB
testcase_24	AC	21 ms 11,680 KB
testcase_25	AC	22 ms 11,552 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n"
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vld = vector<long double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvs = vector<vector<string>>;
using vvc = vector<vector<char>>;
using vvd = vector<vector<double>>;
using vvld = vector<vector<long double>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int INF = 1e9;
const ll LINF = 2e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
bool ispow2(int i) { return i && (i & -i) == i; }
bool ispow2(ll i) { return i && (i & -i) == i; }
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

static uint32_t RandXor(){
    static uint32_t x=123456789;
    static uint32_t y=362436069;
    static uint32_t z=521288629;
    static uint32_t w=88675123;
    uint32_t t;
 
    t=x^(x<<11);
    x=y; y=z; z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}

static double Rand01(){
    return (RandXor()+0.5)*(1.0/UINT_MAX);
}

struct sieve{
    vector<bool> is_prime;
    vector<int> min_factor,primes;

    sieve(int N): is_prime(N+1,true),min_factor(N+1,-1){
        is_prime[1]=false;
        min_factor[1]=1;
        for(int i=2;i<=N;i++){
            if(!is_prime[i]) continue;
            primes.push_back(i);
            min_factor[i]=i;
            for(int j=i;j<=N;j+=i){
                is_prime[j]=false;
                if(min_factor[j]==-1) min_factor[j]=i;
            }
        }
    }

    vector<pair<int,int>> factorize(int n){
        vector<pair<int,int>> ret;
        while(n>1){
            int p=min_factor[n];
            int e=0;
            while(n%p==0){
                e++;
                n/=p;
            }
            ret.emplace_back(p,e);
        }
        return ret;
    }
};

template <typename T = int>
struct Edge{
    int from, to;
    T cost;
    int idx;
    Edge() = default;
    Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}
    operator int() const { return to; }
};

template <typename T = int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int es;
    Graph() = default;
    explicit Graph(int n) : g(n), es(0) {}
    size_t size() const{
        return g.size();
    }

    void add_directed_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es++);
    }

    void add_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }

    void read(int M, int padding = -1, bool weighted = false, bool directed = false){
        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if (weighted) cin >> c;
            if (directed) add_directed_edge(a, b, c);
            else add_edge(a, b, c);
        }
    }

    inline vector<Edge<T>> &operator[](const int &k){
        return g[k];
    }

    inline const vector<Edge<T>> &operator[](const int &k) const{
        return g[k];
    }
};

template <typename T = int>
using Edges = vector<Edge<T>>;

template <typename G>
struct StronglyConnectedComponent{
private:
    G g;
    const int V;
    int cnt;
    vector<int> in,low;
    stack<int> st;
    void dfs(const int v,int &time){
        in[v]=time;
        low[v]=time;
        time++;
        st.push(v);
        for(auto nv:g[v]){
            if(in[nv]<0){
                dfs(nv,time);
                low[v]=min(low[v],low[nv]);
            }
            else if(rev[nv]<0){
                low[v]=min(low[v],in[nv]);
            }
        }
        if(in[v]==low[v]){
            while(true){
                const int u=st.top();
                st.pop();
                rev[u]=cnt;
                if(u==v) break;
            }
            cnt++;
        }
    }

public:
    vector<vector<int>> members;
    vector<int> rev;

    StronglyConnectedComponent(G &_g): 
        g(_g),V(_g.size()),cnt(0),in(_g.size(),-1),low(_g.size()),
        rev(_g.size(),-1){
        int time=0;
        for(int i=0;i<V;i++){
            if(in[i]<0) dfs(i,time);
        }
        for(int i=0;i<V;i++) rev[i]=cnt-rev[i]-1;
        members.resize(cnt);
        for(int i=0;i<V;i++) members[rev[i]].push_back(i);
    }
};

void solve(){
    int N;
    cin>>N;
    vs A(N),B(N);
    rep(i,N) cin>>A[i]>>B[i];
    sieve SE(1000000);
    vi P(1000000);
    for(auto p:SE.primes) P[p]++;
    if(N==1){
        string s1=A[0]+B[0],s2=B[0]+A[0];
        yn(!P[stoi(s1)] || !P[stoi(s2)]);
    }
    Graph<int> G(2*N);
    rep(i,N){
        rep(j,i){
            // S,T
            string s1=A[i]+A[j],t1=B[j]+B[i];
            if(P[stoi(s1)] || P[stoi(t1)]){
                G.add_directed_edge(i,j);
                G.add_directed_edge(j+N,i+N);
            }
            // S,S
            string s2=A[i]+B[j],t2=A[j]+B[i];
            if(P[stoi(s2)] || P[stoi(t2)]){
                G.add_directed_edge(i,j+N);
                G.add_directed_edge(j,i+N);
            }
            // T,T
            string s3=B[i]+A[j],t3=B[j]+A[i];
            if(P[stoi(s3)] || P[stoi(t3)]){
                G.add_directed_edge(i+N,j);
                G.add_directed_edge(j+N,i);
            }
            // T,S
            string s4=B[i]+B[j],t4=A[j]+A[i];
            if(P[stoi(s4)] || P[stoi(t4)]){
                G.add_directed_edge(i+N,j+N);
                G.add_directed_edge(j,i);
            }
        }
    }
    rep(i,N){
        string s1=A[i]+B[i];
        if(P[stoi(s1)]){
            rep(j,N){
                if(i==j) continue;
                G.add_directed_edge(j,i+N);
                G.add_directed_edge(j+N,i+N);
                G.add_directed_edge(i,j);
                G.add_directed_edge(i,j+N);
            }
        }
        string s2=B[i]+A[i];
        if(P[stoi(s2)]){
            rep(j,N){
                if(i==j) continue;
                G.add_directed_edge(j,i);
                G.add_directed_edge(j+N,i);
                G.add_directed_edge(i+N,j);
                G.add_directed_edge(i+N,j+N);
            }
        }
    }
    StronglyConnectedComponent<Graph<int>> SCC(G);
    vi num(2*N);
    auto mem=SCC.members;
    rep(i,sz(mem)) for(auto v:mem[i]) num[v]=i;
    bool flg=true;
    rep(i,N) if(num[i]==num[i+N]) flg=false;
    yn(flg);
}

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

    solve();
}

yukicoder

結果

テストケース

ソースコード