이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
void solve(){
int n, m;
cin >> n >> m;
vector<pair<int,int>>monsters(m);
vector<unordered_set<int>>pos(n);
for (int i = 0; i < m; i++){
int b, p;
cin >> b >> p;
pos[b].insert(p);
monsters[i] = {b,p};
}
vector<long long>dp(n, (long long)1e18);
dp[monsters[0].first] = 0;
vector<int>vis(n, 0);
priority_queue<pair<long long,int>>pq;
pq.push({0,monsters[0].first});
while(!pq.empty()){
long long dst = -pq.top().first;
int b = pq.top().second;
pq.pop();
//node + pow * x = mn
if (dp[b] != dst)continue;
if (b == monsters[1].first){
cout << dst << endl;
return ;
}
if (vis[b])continue;
vis[b] = 1;
for (auto p : pos[b]){
for (int i = 1; i <= n / p; i++){
int right = b + i * p;
int left = b - i * p;
if (left >= 0){
if (dp[left] > dst + i){
dp[left] = dst + i;
pq.push({-dst-i,left});
}
}
if (right <= n - 1){
if (dp[right] > dst + i){
dp[right] = dst + i;
pq.push({-dst-i,right});
}
}
}
}
}
cout << - 1 << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |