Submission #308491

#	Time	Username	Problem	Language	Result	Execution time	Memory
308491		ErdosSzekeres	Lutrija (COCI19_lutrija)	C++14	70 / 70	169 ms	18684 KiB

lutrija

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
const int MAXN = 1e7 + 7;
vector<int> G[20];
int dist[20], pred[20];
vector<ll> primos;
bool composto[MAXN];
bool primality_test(ll x){
    if(x < MAXN)return !composto[x];
    //x eh bem grande
    for(int i=0; i<(int)primos.size(); i++){
        if(x%primos[i] == 0)return false;
    }
    return true;
}
int main(){
    fastio;
    composto[1] = true;
    for(int i=2; i<MAXN; i++){
        if(composto[i])continue;
        primos.push_back(i);
        for(int j=2*i; j<MAXN; j+=i)composto[j]=true;
    }
    ll a,b; cin>>a>>b;
    set<ll> candidates;
    candidates.insert(2);
    candidates.insert(a-2);candidates.insert(a);candidates.insert(a+2);
    candidates.insert(b-2);candidates.insert(b);candidates.insert(b+2);
    vector<ll> nodes; int cnt = 0;
    int source, dest;
    for(auto it : candidates){
        if(it < 2)continue;
        if(it == a){nodes.push_back(it); source = cnt++; continue;}
        if(it == b){nodes.push_back(it); dest = cnt++; continue;}
        if(!primality_test(it))continue;
        nodes.push_back(it);
        cnt++;
    }
    for(int i=0; i<(int)nodes.size(); i++){
        dist[i] = MAXN;
        for(int j=i+1; j<(int)nodes.size(); j++){
            ll val = nodes[j] - nodes[i];
            if(val < 0)val = -val;
            if(primality_test(val)){
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    dist[source] = 0; pred[source] = -1;
    queue<int> bfs; bfs.push(source);
    while(!bfs.empty()){
        int u = bfs.front(); bfs.pop();
        for(int viz : G[u]){
            if(dist[viz] > dist[u] + 1){
                dist[viz] = dist[u] + 1;
                pred[viz] = u;
                bfs.push(viz);
            }
        }
    }
    if(dist[dest] == MAXN){
        cout<<"-1"<<endl;
    }else{
        cout << dist[dest] + 1 << endl;
        vector<ll> aux;
        while(dest != -1){
            aux.push_back(nodes[dest]);
            dest = pred[dest];
        }
        reverse(aux.begin(), aux.end());
        for(ll it : aux){
            cout<<it<<" ";
        }
        cout<<endl;
    }
}

Compilation message (stderr)

lutrija.cpp: In function 'int main()':
lutrija.cpp:64:17: warning: 'dest' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     if(dist[dest] == MAXN){
      |        ~~~~~~~~~^

• 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