#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAXN = 300+5;
ll n,k,m;
ll a[MAXN];
ll b[MAXN];
vector<ll> op[MAXN];
bool inRange(ll p, ll a, ll b){
if(a<b){ // iz a de
if(a<=p && a+k>=p) return true;
}else{
if(a>=p && a-k<=p) return true;
}
return false;
}
ll next(ll p, ll a, ll b){
if(a<b){ // iz a de
if(p+1<=b) return p+1;
}else{
if(p-1>=b) return p-1;
}
return -1;
}
ll bfs( ll pini , ll pfin ){
//[][] nd y linea
bool vis[MAXN][MAXN]; mset(vis,false);
ll dis[MAXN][MAXN]; mset(dis,-1);
queue< pair< ll , pair<ll,ll> > > q;
for(auto i:op[pini]) q.push({1,{pini,i}});
while(!q.empty()){
ll nd = q.front().snd.fst;
ll line = q.front().snd.snd;
ll cost = q.front().fst;
q.pop();
if(vis[nd][line]) continue;
//cout<<nd<<" "<<line<<" "<<cost<<'\n';
vis[nd][line]=true;
dis[nd][line]=cost;
if(next(nd,a[line],b[line])!=-1){
q.push({(cost),{next(nd,a[line],b[line]),line}});
}
for(auto i:op[nd]) q.push({cost+1,{nd,i}});
}
ll res = MAXN;
forn(i,0,m){
if(vis[pfin][i]){
res=min(res,dis[pfin][i]);
}
}
if(res==MAXN) return -1;
return res;
}
int main(){ FIN;
cin>>n>>k>>m; k--;
forn(i,0,m) cin>>a[i]>>b[i];
forn(p,0,n+1){
forn(i,0,m){
if(inRange(p,a[i],b[i])) op[p].pb(i);
}
}
ll q; cin>>q;
while(q--){
ll ini,fin; cin>>ini>>fin;
cout<<bfs(ini,fin)<<'\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |