oj.uz

Submission #903988

# Submission time Handle Problem Language Result Execution time Memory
903988 2024-01-11T16:10:25 Z vjudge1 Lutrija (COCI19_lutrija) C++17
42 / 70
 2 ms 604 KB 
#include<bits/stdc++.h>
using namespace std;
const int mxN = 1005;
vector<int> G[mxN];
bool isPrime(int n){
    if(n < 2)return 0;
	if(n == 2)return 1;
	if(n % 2 == 0)return 0;
	for(int i = 3;i * i <= n;i += 2){
		if(n % i == 0)return 0;
	}
	return 1;
}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b;
  cin >> a >> b;
  for(int i = 2;i <= 1000;++i){
  	if(isPrime(i)){
  		for(int j = 2;j <= 1000;++j){
  			if(isPrime(abs(i - j)) && isPrime(j)){
  				G[i].push_back(j);
  				G[j].push_back(i);
  			}
  		}
  	}
  }
  vector<int>dist(1001, 1e9);
  vector<int>par(1001);
  par[a] = a;
  queue<int>Q;
  Q.push(a);
  dist[a] = 0;
  while(!Q.empty()){
  	int cur = Q.front();
  	Q.pop();
  	for(int &v : G[cur]){
  		if(dist[v] > dist[cur] + 1){
  			dist[v] = dist[cur] + 1;
  			par[v] = cur;
  			Q.push(v);
  		}
  	}
  }
  if(dist[b] != 1e9){
    vector<int>path;
    int node = b;
    while(node != a){
    	path.push_back(node);
    	node = par[node];
    } 
    path.push_back(a);
    reverse(path.begin(), path.end());
    cout << path.size() << '\n';
    for(int &i : path)cout << i << " ";
  }
  else{
  	cout << -1;
  }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -