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 ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 3e4 + 5;
int B[maxn],P[maxn];
void input(int n){
for (int i = 0 ; i < n ; i++)
cin >> B[i] >> P[i];
}
namespace sub1{
const int K = 2e3 + 5;
bool check(int n){
return (n <= K);
}
bool mark[K][K],vis[K];
int dp[K];
vector <vector<pir>> vec(100*K);
vector <vector<int>> doge(K);
void bfs(int n,int N){
vec[0].push_back({B[0],P[0]});
for (int len = 0 ; len < 100*N ; len++)
for (pir t : vec[len]){
int Bi = t.fi,Pi = t.se;
if (mark[Bi][Pi]) continue;
mark[Bi][Pi] = 1;
if (!vis[Bi])
dp[Bi] = len;
if (Bi + Pi < N)
vec[len + 1].push_back({Bi + Pi,Pi});
if (Bi - Pi >= 0)
vec[len + 1].push_back({Bi - Pi,Pi});
if (!vis[Bi])
for (int p : doge[Bi]){
if (Bi + p < N)
vec[len + 1].push_back({Bi + p,p});
if (Bi - p >= 0)
vec[len + 1].push_back({Bi - p,p});
}
vis[Bi] = 1;
}
}
int solve(int n,int N){
//dp[i][k] : position i, jump k
for (int i = 0 ; i < n ; i++)
doge[B[i]].push_back(P[i]);
bfs(n,N);
if (!vis[B[1]]) return -1;
return dp[B[1]];
}
}
namespace sub2{
const int block = 150;
bool vis[maxn];
bool mark[maxn][block];
int dp[maxn];
vector <vector<pir>> vec(maxn*block + 10);
vector <vector<int>> doge(maxn);
void bfs(int n,int N){
vec[0].push_back({B[0],P[0]});
for (int len = 0 ; len < N * block ; len++)
for (pir t : vec[len]){
int Bi = t.fi,Pi = t.se;
if (Pi <= block && mark[Bi][Pi]) continue;
if (Pi <= block) mark[Bi][Pi] = 1;
if (!vis[Bi]) dp[Bi] = len;
if (!vis[Bi])
for (int p : doge[Bi])
if (p > block){
for (int x = Bi + p ; x < N ; x += p)
if (x < N && !vis[x])
vec[len + (x - Bi)/p].push_back({x,p});
for (int x = Bi - p ; x >= 0 ; x -= p)
if (x >= 0 && !vis[x])
vec[len + (Bi - x)/p].push_back({x,p});
}
if (!vis[Bi])
for (int p : doge[Bi])
if (p <= block){
if (Bi + p < N)
vec[len + 1].push_back({Bi + p,p});
if (Bi - p >= 0)
vec[len + 1].push_back({Bi - p,p});
}
if (Pi <= block && Bi + Pi < N)
vec[len + 1].push_back({Bi + Pi,Pi});
if (Pi <= block && Bi - Pi >= 0)
vec[len + 1].push_back({Bi - Pi,Pi});
vis[Bi] = 1;
}
}
int solve(int n,int N){
for (int i = 0 ; i < n ; i++)
doge[B[i]].push_back(P[i]);
bfs(n,N);
if (!vis[B[1]]) return -1;
return dp[B[1]];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int N,n;
cin >> N >> n;
input(n);
if (sub1::check(N))
cout << sub1::solve(n,N);else
cout << sub2::solve(n,N);
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... |