제출 #299225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299225		ryuku1110	Lutrija (COCI19_lutrija)	C++14	42 / 70	2 ms	512 KiB

lutrija

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
vector <int> v;
bool visit[1001];
vector <int> adj[1001];
int a, b;

bool prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= sqrt(x); ++ i) {
        if (x % i == 0) return false;
    }
    return true;
}
int par[1001];
void dfs(int u) {
    visit[u] = true;
    for (int v : adj[u]) {
        if (visit[v]) continue;
        else {
            par[v] = u;
            dfs(v);
        }
    }
}
int main() {
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> a >> b;
    
    v.push_back(a);
    v.push_back(b);

    for (int i = a - 2; i <= a + 2; ++ i) {
        if (prime(i) && i != a) v.push_back(i);
    }
    for (int i = b - 2; i <= b + 2; ++ i) {
        if (prime(i) && i != b) v.push_back(i);
    }
    v.push_back(2);
    sort(v.begin(), v.end());
    for (int i : v) {
        for (int j : v) {
            if (i != j && prime(abs(j - i))) {
                adj[i].pb(j);
                adj[j].pb(i);
            }
        }
    }
    dfs(a);
    if (!visit[b]) {
        cout << -1;
        return 0;
    }
    vector <int> ans;
    ans.pb(b);
    while (par[b] != 0) {
        ans.pb(par[b]);
        b = par[b];
    }
    
    cout << ans.size() << endl;
    for (int i = ans.size() - 1;i >= 0; -- i) cout << ans[i] << " ";
    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: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7