oj.uz

Submission #344554

# Submission time Handle Problem Language Result Execution time Memory
344554 2021-01-06T05:48:01 Z limabeans Lutrija (COCI19_lutrija) C++17
70 / 70
 574 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



bool isprime(ll x) {
    if (x<=1) return false;
    
    for (ll i=2; i*i<=x; i++) {
	if (x%i==0) return false;
    }
    
    return true;
}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    assert(isprime(41));

    ll a,b;
    cin>>a>>b;

    //0->2->1->0->2->0.. mod3

    map<ll,vector<ll>> g;
    vector<ll> tmp = {a-2,a,a+2,b-2,b,b+2,2};
    vector<ll> nodes;
    for (ll x: tmp) {
	if (isprime(x)) {
	    nodes.push_back(x);
	}
    }
    
    for (int i=0; i<(int)nodes.size(); i++) {
	for (int j=i+1; j<(int)nodes.size(); j++) {
	    ll x = nodes[i];
	    ll y = nodes[j];
	    if (isprime(abs(x-y))) {
		g[x].push_back(y);
		g[y].push_back(x);
	    }
	}
    }


    map<ll,ll> par;

    queue<ll> qq;
    qq.push(a);
    while (qq.size()) {
	ll at = qq.front();
	qq.pop();
	for (ll to: g[at]) {
	    if (!par.count(to)) {
		par[to] = at;
		qq.push(to);
	    }
	}
    }


    if (!par.count(b)) out(-1);
    vector<ll> path;
    while (b != a) {
	path.push_back(b);
	b = par[b];
    }
    path.push_back(a);

    cout<<path.size()<<"\n";
    while (path.size()) {
	cout<<path.back()<<" ";
	path.pop_back();
    }
    cout<<endl;
    
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 492 KB Output is correct
2 Correct 328 ms 392 KB Output is correct
3 Correct 574 ms 492 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 492 KB Output is correct
2 Correct 295 ms 364 KB Output is correct
3 Correct 411 ms 364 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 492 KB Output is correct
2 Correct 344 ms 620 KB Output is correct
3 Correct 378 ms 364 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 388 KB Output is correct
2 Correct 239 ms 364 KB Output is correct
3 Correct 135 ms 364 KB Output is correct