This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=30005;
int n,m,b[N],p[N],d[N];
vector<pii>adj[N];
vector<int>have[N];
bool Have(int pos, int val)
{
return binary_search(have[pos].begin(), have[pos].end(), val);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>b[i]>>p[i];
b[i]++;
have[b[i]].push_back(p[i]);
}
for(int i=1;i<=n;i++)
{
sort(have[i].begin(),have[i].end());
have[i].erase(unique(have[i].begin(),have[i].end()),have[i].end());
}
memset(d,-1,sizeof d);
d[b[1]]=0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push(mp(0,b[1]));
while(!pq.empty())
{
auto u=pq.top();
pq.pop();
if(u.fi!=d[u.se]) continue;
for(auto&x:have[u.se])
{
int cnt=0,cur=u.se;
while(cur+x<=n)
{
cnt++;
cur+=x;
if(d[cur]==-1||d[cur]>u.fi+cnt)
{
d[cur]=u.fi+cnt;
pq.push(mp(d[cur],cur));
}
if(Have(cur,x)) break;
}
cur=u.se;
cnt=0;
while(cur-x>=1)
{
cnt++;
cur-=x;
if(d[cur]==-1||d[cur]>u.fi+cnt)
{
d[cur]=u.fi+cnt;
pq.push(mp(d[cur],cur));
}
if(Have(cur,x)) break;
}
}
}
cout<<d[b[2]];
}
# | 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... |