oj.uz

Submission #308491

# Submission time Handle Problem Language Result Execution time Memory
308491 2020-10-01T12:37:07 Z ErdosSzekeres Lutrija (COCI19_lutrija) C++14
70 / 70
 169 ms 18684 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 18536 KB Output is correct
2 Correct 137 ms 18684 KB Output is correct
3 Correct 139 ms 18408 KB Output is correct
4 Correct 138 ms 18408 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 18412 KB Output is correct
2 Correct 138 ms 18536 KB Output is correct
3 Correct 140 ms 18408 KB Output is correct
4 Correct 151 ms 18468 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 18408 KB Output is correct
2 Correct 161 ms 18540 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18536 KB Output is correct
2 Correct 144 ms 18664 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 18412 KB Output is correct
2 Correct 142 ms 18536 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 18468 KB Output is correct
2 Correct 153 ms 18540 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 18432 KB Output is correct
2 Correct 153 ms 18404 KB Output is correct
3 Correct 154 ms 18536 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 18412 KB Output is correct
2 Correct 155 ms 18408 KB Output is correct
3 Correct 144 ms 18408 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 18412 KB Output is correct
2 Correct 153 ms 18408 KB Output is correct
3 Correct 149 ms 18536 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 18408 KB Output is correct
2 Correct 153 ms 18532 KB Output is correct
3 Correct 154 ms 18408 KB Output is correct