oj.uz

Submission #903994

# Submission time Handle Problem Language Result Execution time Memory
903994 2024-01-11T16:29:12 Z vjudge1 Lutrija (COCI19_lutrija) C++17
42 / 70
 1 ms 468 KB 
#include<bits/stdc++.h>
using namespace std;
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;
  map<long long, vector<long long>>G;
  for(int i = -2;i <= 2;i += 2){
  	if(i && isPrime(a + i)){
  		G[a].push_back(a + i);
  		G[a + i].push_back(a);
  	}
  	for(int j = -2;j <= 2;j += 2){
  		if(isPrime(a + i) && isPrime(b + j) && isPrime(abs(a + i - b - j))){
  			G[a + i].push_back(b + j);
  			G[b + j].push_back(a + i);
  		}
  		if(isPrime(a + i) && isPrime(abs(a + i - 2))){
  			G[2].push_back(a + i);
  			G[a + i].push_back(2);
  		}
  		if(isPrime(b + j) && isPrime(abs(b + j - 2))){
  			G[2].push_back(b + j);
  			G[b + j].push_back(2);
  		}
  	}
  }
  for(int j = -2;j <= 2;j += 2){
  	if(j && isPrime(b + j)){
  		G[b].push_back(b + j);
  		G[b + j].push_back(b);
  	}
  }
  map<long long, int>dist;
  dist[a] = 0;
  map<long long, int>par;
  par[a] = a;
  queue<int>q;
  q.push(a);
  while(!q.empty()){
  	long long cur = q.front();
    q.pop();
    for(long long &v : G[cur]){
      if(!dist.count(v) || dist[v] > dist[cur] + 1){
      	dist[v] = dist[cur] + 1;
      	par[v] = cur;
      	q.push(v);
      }
    }
  }
  if(!dist.count(b)){
  	cout << -1;
  }
  else{
  	vector<long long>path;
  	long long 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(long long &v : path)cout << v << " ";
  }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 468 KB Output is correct

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -