#include <bits/stdc++.h>
using namespace std;
struct Event {
int modl, modr, type;
Event() {}
Event(int _modl, int _modr, int _type) : modl(_modl), modr(_modr), type(_type) {}
};
void solve() {
int N, K;
cin >> N >> K;
int M;
cin >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
A[i]--, B[i]--;
}
vector<vector<Event>> events(N);
for (int i = 0; i < M; i++) {
if (A[i] < B[i]) {
events[A[i]].emplace_back(N, B[i], 1);
events[min(A[i] + K - 1, B[i])].emplace_back(N, B[i], -1);
} else {
events[max(A[i] - K + 1, B[i])].emplace_back(B[i], -1, 1);
events[A[i]].emplace_back(B[i], -1, -1);
}
}
vector<int> L(N), R(N);
multiset<int> sl, sr;
for (int i = 0; i < N; i++) {
L[i] = i, R[i] = i;
for (auto [modl, modr, type] : events[i]) {
if (type == 1) {
sl.insert(modl);
sr.insert(modr);
}
}
if (!sl.empty()) {
L[i] = min(L[i], *sl.begin());
R[i] = max(R[i], *sr.rbegin());
}
for (auto [modl, modr, type] : events[i]) {
if (type == -1) {
sl.erase(sl.find(modl));
sr.erase(sr.find(modr));
}
}
}
int Q;
cin >> Q;
while (Q--) {
int S, T;
cin >> S >> T;
S--, T--;
queue<int> q;
set<int> unvisited;
for (int i = 0; i < N; i++) {
if (i != S) {
unvisited.insert(i);
}
}
vector<int> dist(N, N);
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
auto it = unvisited.lower_bound(L[u]);
while (it != unvisited.end() && *it <= R[u]) {
dist[*it] = dist[u] + 1;
q.push(*it);
it = next(it);
unvisited.erase(prev(it));
}
}
cout << (dist[T] == N ? -1 : dist[T]) << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
320 KB |
Output is correct |
7 |
Correct |
9 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
10 ms |
488 KB |
Output is correct |
10 |
Correct |
0 ms |
320 KB |
Output is correct |
11 |
Correct |
10 ms |
340 KB |
Output is correct |
12 |
Correct |
8 ms |
360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
320 KB |
Output is correct |
7 |
Correct |
9 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
10 ms |
488 KB |
Output is correct |
10 |
Correct |
0 ms |
320 KB |
Output is correct |
11 |
Correct |
10 ms |
340 KB |
Output is correct |
12 |
Correct |
8 ms |
360 KB |
Output is correct |
13 |
Correct |
525 ms |
576 KB |
Output is correct |
14 |
Correct |
502 ms |
564 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
511 ms |
604 KB |
Output is correct |
17 |
Correct |
468 ms |
596 KB |
Output is correct |
18 |
Correct |
552 ms |
688 KB |
Output is correct |
19 |
Correct |
425 ms |
600 KB |
Output is correct |
20 |
Correct |
506 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
592 KB |
Output is correct |
22 |
Correct |
434 ms |
608 KB |
Output is correct |
23 |
Correct |
418 ms |
600 KB |
Output is correct |
24 |
Correct |
382 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
12680 KB |
Output is correct |
2 |
Correct |
64 ms |
12584 KB |
Output is correct |
3 |
Correct |
71 ms |
13384 KB |
Output is correct |
4 |
Correct |
66 ms |
12252 KB |
Output is correct |
5 |
Correct |
244 ms |
20240 KB |
Output is correct |
6 |
Correct |
102 ms |
18908 KB |
Output is correct |
7 |
Correct |
223 ms |
21824 KB |
Output is correct |
8 |
Correct |
129 ms |
14684 KB |
Output is correct |
9 |
Correct |
137 ms |
14836 KB |
Output is correct |
10 |
Correct |
144 ms |
20180 KB |
Output is correct |
11 |
Correct |
141 ms |
20172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2011 ms |
13388 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2040 ms |
20624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
320 KB |
Output is correct |
7 |
Correct |
9 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
10 ms |
488 KB |
Output is correct |
10 |
Correct |
0 ms |
320 KB |
Output is correct |
11 |
Correct |
10 ms |
340 KB |
Output is correct |
12 |
Correct |
8 ms |
360 KB |
Output is correct |
13 |
Correct |
525 ms |
576 KB |
Output is correct |
14 |
Correct |
502 ms |
564 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
511 ms |
604 KB |
Output is correct |
17 |
Correct |
468 ms |
596 KB |
Output is correct |
18 |
Correct |
552 ms |
688 KB |
Output is correct |
19 |
Correct |
425 ms |
600 KB |
Output is correct |
20 |
Correct |
506 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
592 KB |
Output is correct |
22 |
Correct |
434 ms |
608 KB |
Output is correct |
23 |
Correct |
418 ms |
600 KB |
Output is correct |
24 |
Correct |
382 ms |
600 KB |
Output is correct |
25 |
Correct |
59 ms |
12680 KB |
Output is correct |
26 |
Correct |
64 ms |
12584 KB |
Output is correct |
27 |
Correct |
71 ms |
13384 KB |
Output is correct |
28 |
Correct |
66 ms |
12252 KB |
Output is correct |
29 |
Correct |
244 ms |
20240 KB |
Output is correct |
30 |
Correct |
102 ms |
18908 KB |
Output is correct |
31 |
Correct |
223 ms |
21824 KB |
Output is correct |
32 |
Correct |
129 ms |
14684 KB |
Output is correct |
33 |
Correct |
137 ms |
14836 KB |
Output is correct |
34 |
Correct |
144 ms |
20180 KB |
Output is correct |
35 |
Correct |
141 ms |
20172 KB |
Output is correct |
36 |
Execution timed out |
2011 ms |
13388 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |