oj.uz

Submission #1090517

# Submission time Handle Problem Language Result Execution time Memory
1090517 2024-09-18T12:23:50 Z Vkrisztian01 Lutrija (COCI19_lutrija) C++14
70 / 70
 133 ms 436 KB 
#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

bool is_prime(ll a) {

    if( a == 0 || a == 1) return false;

    ll k = sqrt(a);
    for(ll i = 2; i <= k; i++)
        if(a % i == 0) return false;
    return true;
}

void dfs(int v,vector<vector<int> > &adj,vector<int> &origin) {

    for(int to : adj[v]) {

        if(origin[to] ==-1) {

            origin[to] = v;
            dfs(to,adj,origin);

        }

    }


}

int main()
{
    ll a, b;
    cin >> a >> b;

    if(a == b) {

        cout << 1 << "\n";
        cout << a;
        return 0;

    }

    vector<ll> v = {a,2,a - 2,a + 2,b - 2,b + 2,b};

    for(int i = 0; i < v.size(); i++)
        if(!is_prime(v[i])) {v.erase(v.begin() + i); --i;}

    int n = v.size();

    vector<vector<int> > adj(n);

    for(int i = 0; i < n; i++) {

        for(int j = i + 1; j < n; j++) {

            if(is_prime(abs(v[i] - v[j])))
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }

        }
    }

    vector<int> origin(n, -1);
    origin[0] = -2;
    dfs(0,adj,origin);

    if(origin[n - 1] == -1)
    {
        cout<<-1;
        return 0;
    }

    vector<ll> ans;
    int k = n-1;

    while(k != -2)
    {
        ans.push_back(v[k]);
        k = origin[k];
    }

    reverse(ans.begin(),ans.end());

    cout<<ans.size()<<"\n";

    for(ll x : ans) cout<<x<<" ";

    return 0;
}

Compilation message

lutrija.cpp: In function 'int main()':
lutrija.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 348 KB Output is correct
2 Correct 77 ms 412 KB Output is correct
3 Correct 133 ms 348 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 356 KB Output is correct
2 Correct 69 ms 344 KB Output is correct
3 Correct 98 ms 348 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 348 KB Output is correct
2 Correct 79 ms 412 KB Output is correct
3 Correct 90 ms 344 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 348 KB Output is correct
2 Correct 57 ms 344 KB Output is correct
3 Correct 33 ms 348 KB Output is correct