Submission #1090042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090042		Hora000	Lutrija (COCI19_lutrija)	C++14	70 / 70	852 ms	412 KiB

lutrija

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

    //ofstream cout("c.out"); 
vector<vector<int>> g;

bool prim(long long x){
    if(x <= 1) return false;
    for(long long i = 2; i <= sqrt(x); i++){
        if(x % i == 0) return false;
    }
    return true;
}

vector<long long> bfs(int v){
    vector<bool> vis(7);
    queue<int> q;
    vector<int> p(7, -1);
    q.push(v);
    vis[v] = true;
    while(!q.empty()){
        for(auto x : g[q.front()]){
            if(!vis[x]){
                vis[x] = true;
                p[x] = q.front();
                q.push(x);
            }
        }
        q.pop();
    }
    if(p[6] == -1) return {(long long)-1};
    vector<long long> r;
    int c = 6;
    while(p[c] != -1){
        r.push_back(c);
        c = p[c];
    }
    r.push_back(c);
    reverse(r.begin(), r.end());
    return r;
}

int main(){
    //ifstream cin("c.in"); 
    long long a, b;
    cin >> a >> b;
    g.resize(7);
    //0 a, 1 a + 2, 2 a - 2, 3 2, 4 b - 2, 5 b + 2, 6 b
    vector<long long> e = {a, a + 2, a - 2, 2, b - 2, b + 2, b};
    for(int i = 0; i < 7; i++){
        for(int j = 0; j < 7; j++){
            if(prim(abs(e[i] - e[j])) && prim(e[i]) && prim(e[j])){
                g[i].push_back(j);
            }
        }
    }
    vector<long long> ans = bfs(0);
    if(ans[0] == -1) cout << "-1\n";
    else{
        cout << ans.size() << "\n";
        for(auto x : ans) cout << e[x] << " ";
    }
}

• 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