Submission #1370389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370389		AliMark71	Lutrija (COCI19_lutrija)	C++20	35 / 70	63 ms	768 KiB

lutrija

//
//  main.cpp
//  IntensiveCamp 1 2026
//
//  Created by Ali AlSalman on 27/04/2026.
//
 
#include <bits/stdc++.h>


//#define INTERACTIVE
//#define TESTCASES
//#define FUNCTIONAL
//#define SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__
 
#ifndef INTERACTIVE
#define endl '\n'
#endif
 
template<typename T>
using vec = std::vector<T>;
using namespace std;

#define all(x) x.begin(), x.end()

struct G {
    int size;
    vec<vec<int>> adj;
    vec<array<int, 2>> dis;
    G(int n) : size(n), adj(n), dis(n, {-1, -1}) {}
    
    void add(int a, int b) {
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    

    void dist(int a) {
        queue<int> q; q.push(a); dis[a][0] = 0;
        while (!q.empty()) {
            auto u = q.front(); q.pop();
            for (auto v : adj[u]) if (dis[v][0] == -1) {
                dis[v][0] = dis[u][0] + 1;
                dis[v][1] = u;
                q.push(v);
            }
        }
    }
    
    vec<int> shortest(int a, int b) {
        dist(a);
        
        vec<int> path;
        while (b != -1) {
            path.push_back(b);
            b = dis[b][1];
        }
        return path;
    }
};

void solve() {
    vec<bool> p(10000, true);
    for (int i = 2; i < p.size(); i++) if (p[i])
        for (int j = i * i; j < p.size(); j += i)
            p[j] = false;

    G g(10000);
    for (int i = 2; i < 10000; i++) for (int j = 2; j < 10000; j++)
        if (p[i] && p[j] && p[abs(i - j)])
            g.add(i, j);
    
    int a, b;
    cin>>a>>b;
    
    auto path = g.shortest(a, b); reverse(all(path));
    if (path.size() == 1) { cout<<-1<<endl; return; }
    cout<<path.size()<<endl;
    for (auto u : path) cout<<u<<" "; cout<<endl;
    
}
 
#ifndef FUNCTIONAL
int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    
    for (int i = t; i--;) {
#if defined(TESTCASES) && defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
        cout<<"Case "<<t-i<<":\n";
#elif defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
#warning SPOJ_BULLSCHEIßE__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
#endif
        solve();
    }
    return 0;
}
#endif

Compilation message (stderr)

lutrija.cpp:98:69: warning: missing terminating ' character
   98 | #warning SPOJ_BULLSCHEIßE__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
      |                                                                     ^

• Subtask 1: 0 / 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