#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int maxn=3e4+5;
int n,m;
int b[maxn],p[maxn];
vector<int>v[maxn];
set<pair<int,int>>vis;
map<pair<int,int>,int>dis;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0;i < m;i++){
cin >> b[i] >> p[i];
v[b[i]].push_back(p[i]);
}
priority_queue<tuple<int,int,int>>q;
q.push({0,b[0],p[0]});
dis[{b[0],p[0]}] = 0;
while(!q.empty()){
int idx = get<1>(q.top());
int pi = get<2>(q.top());
q.pop();
if(vis.find({idx,pi}) != vis.end()) continue;
vis.insert({idx,pi});
int now = dis[{idx,pi}];
if(idx - pi >= 0){
auto t = dis.find({idx - pi,pi});
if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){
dis[{idx - pi,pi}] = now + 1;
q.push({-now - 1,idx - pi,pi});
}
}
if(idx + pi < n){
auto t = dis.find({idx + pi,pi});
if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){
dis[{idx + pi,pi}] = now + 1;
q.push({-now - 1,idx + pi,pi});
}
}
for(auto i : v[idx]){
if(idx - i >= 0){
auto t = dis.find({idx - i,i});
if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){
dis[{idx - i,i}] = now + 1;
q.push({-now - 1,idx - i,i});
}
}
if(idx + i < n){
auto t = dis.find({idx + i,i});
if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){
dis[{idx + i,i}] = now + 1;
q.push({-now - 1,idx + i,i});
}
}
}
}
int ans = 1e9;
for(auto i : dis){
if(i.first.first == b[1]){
ans = min(ans,i.second);
}
}
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Incorrect |
1 ms |
1040 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
1040 KB |
Output is correct |
4 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
1040 KB |
Output is correct |
3 |
Correct |
1 ms |
1040 KB |
Output is correct |
4 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1036 KB |
Output is correct |
2 |
Correct |
1 ms |
1040 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Incorrect |
1 ms |
1036 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1036 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |