Submission #237783

#	Time	Username	Problem	Language	Result	Execution time	Memory
237783		DavidDamian	Lutrija (COCI19_lutrija)	C++11	70 / 70	269 ms	43756 KiB

lutrija

#include <bits/stdc++.h>
using namespace std;
///Sieve of Eratosthenes
///Graph Theory
///BFS
///Determine an array that has prime difference between any two adjacent elements
int sieve[10000007];
vector<int> primes;
void computeSieve()
{
    int n=1e7+1;
    for(int i=4;i<=n;i+=2){
        sieve[i]=1;
    }
    primes.push_back(2);
    for(int i=3;i<=n;i+=2){
        if(sieve[i]==1) continue;
        primes.push_back(i);
        for(int j=i+i;j<=n;j+=i){
            sieve[j]=1;
        }
    }
}
typedef long long ll;
bool isPrime(ll n)
{
    if(n<2) return false;
    for(int p: primes){
        if((ll)p*(ll)p > n) break;
        if(n%p==0) return false;
    }
    return true;
}
ll A,B;
int d[8];
ll number[8];
int color[8];
int p[8];
vector<int> adjList[8];
int k=3;
void dfs(int u)
{
    color[u]=1;
    for(int v: adjList[u]){
        if(color[v]==0){
            p[v]=u;
            d[v]=d[u]+1;
            dfs(v);
        }
    }
}
int main()
{
    computeSieve();
    cin>>A>>B;
    number[1]=B;
    number[2]=A;
    number[3]=2;
    if(isPrime(A-2)) number[++k]=A-2;
    if(isPrime(A+2)) number[++k]=A+2;
    if(isPrime(B-2)) number[++k]=B-2;
    if(isPrime(B+2)) number[++k]=B+2;
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++){
            ll diff=abs(number[i]-number[j]);
            if(isPrime(diff)){
                adjList[i].push_back(j);
                adjList[j].push_back(i);
            }
        }
    }
    d[1]=1;
    dfs(1);
    if(d[2]==0){
        cout<<-1<<'\n';
        return 0;
    }
    cout<<d[2]<<'\n';
    int u=2;
    while(u!=1){
        cout<<number[u]<<" ";
        u=p[u];
    }
    cout<<number[1]<<'\n';
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7