#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
void file_in(string s)
{
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
void normal()
{
ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
if (power == 0)
return 1;
ll result = ex(base, power / 2);
if (power % 2 == 1)
return(((result * result) % mod) * base) % mod;
else return (result * result) % mod;
}
const int maxn=30005;
int dist[maxn], B[maxn], P[maxn];
vi powers[maxn];
int n,m;
void solve(int s)
{
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(mp(dist[s],s));// first is distance, second is position
pii t;
while(!q.empty())
{
t=q.top(); q.pop();
if(t.f>dist[t.s]) continue;// we only need to find minimum distance, then if already greater than, no need to continue these values;
trav(p,powers[t.s])//powers
{
for(int x=1;t.s+p*x<n;++x)
{
int pos=t.s+p*x;
if(dist[pos]>t.f+x)
{
dist[pos]=t.f+x;//keep updating minimum
q.push(mp(dist[pos],pos));
if(binary_search(all(powers[pos]),p)) break;//if there is a power there so no need to continue the other path
}
}
for(int x=1;t.s-p*x>=0;++x)//duplicate but -p instead of +p
{
int pos=t.s-p*x;
if(dist[pos]>t.f+x)//note that distance always increases
{
dist[pos]=t.f+x;
q.push(mp(dist[pos],pos));
if(binary_search(all(powers[pos]),p)) break;
}
}
}
}
}
void check()
{
int maxi=-1;
FOR(i,0,n)
{
if(dist[i]==(int)1e9)
cout<<"-1";
maxi=max(maxi,dist[i]);
}
cout<<maxi;
}
int main()
{
normal();
cin>>n>>m;
FOR(i,0,m)
{
cin>>B[i]>>P[i];
powers[B[i]].push_back(P[i]);
}
FOR(i,0,n)
{
sort(all(powers[i]));
powers[i].erase(unique(all(powers[i])),powers[i].end());//erase duplicates
}
memset(dist,(int)1e9, n);
dist[B[0]]=0;//first move must be 0
solve(B[0]);
check();
return 0;
}
Compilation message
skyscraper.cpp: In function 'void file_in(std::string)':
skyscraper.cpp:37:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
