#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1e5+5;
int N,K,M,Q;
vector<int> adj[MX];
int dist[MX];
int A[MX], B[MX];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>K>>M;
for(int i=1;i<=M;i++) cin>>A[i]>>B[i];
cin>>Q;
for(int i=1;i<=Q;i++) {
int s, t;
cin>>s>>t;
queue<int> q;
for(int i=1;i<=N;i++) dist[i]=-1;
dist[s]=0;
q.push(s);
while(!q.empty()) {
int p=q.front(); q.pop();
for(int i=1;i<=M;i++) {
if(A[i]<B[i]) {
int m=min(A[i]+K-1,B[i]-1);
if(A[i]<=p&&p<=m) {
for(int j=A[i];j<=B[i];j++)
if(dist[j]==-1) {
dist[j]=dist[p]+1;
q.push(j);
}
}
} else {
int m=max(A[i]-K+1,B[i]+1);
if(m<=p&&p<=A[i]) {
for(int j=B[i];j<=A[i];j++)
if(dist[j]==-1) {
dist[j]=dist[p]+1;
q.push(j);
}
}
}
}
}
cout<<dist[t]<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
3800 KB |
Output is correct |
2 |
Correct |
60 ms |
3676 KB |
Output is correct |
3 |
Correct |
3 ms |
3672 KB |
Output is correct |
4 |
Correct |
472 ms |
3784 KB |
Output is correct |
5 |
Correct |
60 ms |
3928 KB |
Output is correct |
6 |
Execution timed out |
2059 ms |
3676 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
3800 KB |
Output is correct |
2 |
Correct |
60 ms |
3676 KB |
Output is correct |
3 |
Correct |
3 ms |
3672 KB |
Output is correct |
4 |
Correct |
472 ms |
3784 KB |
Output is correct |
5 |
Correct |
60 ms |
3928 KB |
Output is correct |
6 |
Execution timed out |
2059 ms |
3676 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2101 ms |
4952 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2053 ms |
5212 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2043 ms |
6740 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
3800 KB |
Output is correct |
2 |
Correct |
60 ms |
3676 KB |
Output is correct |
3 |
Correct |
3 ms |
3672 KB |
Output is correct |
4 |
Correct |
472 ms |
3784 KB |
Output is correct |
5 |
Correct |
60 ms |
3928 KB |
Output is correct |
6 |
Execution timed out |
2059 ms |
3676 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |