oj.uz

답안 #299225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299225 2020-09-14T15:06:52 Z ryuku1110 Lutrija (COCI19_lutrija) C++14
42 / 70
 2 ms 512 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #7
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -