#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));
}
}
}
if (K == N - 1) {
vector<vector<int>> nxt(N, vector<int>(20)), lst(N, vector<int>(20));
for (int i = 0; i < N; i++) {
lst[i][0] = L[i];
nxt[i][0] = R[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j + 1 < 20; j++) {
lst[i][j + 1] = lst[lst[i][j]][j];
}
}
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j + 1 < 20; j++) {
nxt[i][j + 1] = nxt[nxt[i][j]][j];
}
}
int Q;
cin >> Q;
while (Q--) {
int S, T;
cin >> S >> T;
S--, T--;
int ans = 0;
if (S < T) {
for (int i = 20 - 1; i >= 0; i--) {
if (nxt[S][i] < T) {
ans += (1 << i);
S = nxt[S][i];
}
}
} else {
for (int i = 20 - 1; i >= 0; i--) {
if (lst[S][i] > T) {
ans += (1 << i);
S = lst[S][i];
}
}
}
cout << (ans == (1 << 20) - 1 ? -1 : ans + 1) << "\n";
}
return;
}
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 |
316 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
9 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
8 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
13 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 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 |
316 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
9 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
8 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
13 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
523 ms |
572 KB |
Output is correct |
14 |
Correct |
504 ms |
556 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
522 ms |
608 KB |
Output is correct |
17 |
Correct |
438 ms |
724 KB |
Output is correct |
18 |
Correct |
3 ms |
980 KB |
Output is correct |
19 |
Correct |
411 ms |
608 KB |
Output is correct |
20 |
Correct |
499 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
976 KB |
Output is correct |
23 |
Correct |
399 ms |
596 KB |
Output is correct |
24 |
Correct |
3 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
11804 KB |
Output is correct |
2 |
Correct |
57 ms |
11700 KB |
Output is correct |
3 |
Correct |
66 ms |
12348 KB |
Output is correct |
4 |
Correct |
65 ms |
11476 KB |
Output is correct |
5 |
Correct |
241 ms |
18052 KB |
Output is correct |
6 |
Correct |
107 ms |
16672 KB |
Output is correct |
7 |
Correct |
201 ms |
34100 KB |
Output is correct |
8 |
Correct |
167 ms |
13768 KB |
Output is correct |
9 |
Correct |
136 ms |
31816 KB |
Output is correct |
10 |
Correct |
139 ms |
18008 KB |
Output is correct |
11 |
Correct |
158 ms |
36712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
138 ms |
30652 KB |
Output is correct |
2 |
Correct |
297 ms |
39492 KB |
Output is correct |
3 |
Correct |
139 ms |
32752 KB |
Output is correct |
4 |
Correct |
203 ms |
36548 KB |
Output is correct |
5 |
Correct |
294 ms |
39112 KB |
Output is correct |
6 |
Correct |
361 ms |
39368 KB |
Output is correct |
7 |
Correct |
186 ms |
39448 KB |
Output is correct |
8 |
Correct |
205 ms |
39552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2047 ms |
18104 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 |
316 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
9 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
8 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
13 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
523 ms |
572 KB |
Output is correct |
14 |
Correct |
504 ms |
556 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
522 ms |
608 KB |
Output is correct |
17 |
Correct |
438 ms |
724 KB |
Output is correct |
18 |
Correct |
3 ms |
980 KB |
Output is correct |
19 |
Correct |
411 ms |
608 KB |
Output is correct |
20 |
Correct |
499 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
976 KB |
Output is correct |
23 |
Correct |
399 ms |
596 KB |
Output is correct |
24 |
Correct |
3 ms |
980 KB |
Output is correct |
25 |
Correct |
56 ms |
11804 KB |
Output is correct |
26 |
Correct |
57 ms |
11700 KB |
Output is correct |
27 |
Correct |
66 ms |
12348 KB |
Output is correct |
28 |
Correct |
65 ms |
11476 KB |
Output is correct |
29 |
Correct |
241 ms |
18052 KB |
Output is correct |
30 |
Correct |
107 ms |
16672 KB |
Output is correct |
31 |
Correct |
201 ms |
34100 KB |
Output is correct |
32 |
Correct |
167 ms |
13768 KB |
Output is correct |
33 |
Correct |
136 ms |
31816 KB |
Output is correct |
34 |
Correct |
139 ms |
18008 KB |
Output is correct |
35 |
Correct |
158 ms |
36712 KB |
Output is correct |
36 |
Correct |
138 ms |
30652 KB |
Output is correct |
37 |
Correct |
297 ms |
39492 KB |
Output is correct |
38 |
Correct |
139 ms |
32752 KB |
Output is correct |
39 |
Correct |
203 ms |
36548 KB |
Output is correct |
40 |
Correct |
294 ms |
39112 KB |
Output is correct |
41 |
Correct |
361 ms |
39368 KB |
Output is correct |
42 |
Correct |
186 ms |
39448 KB |
Output is correct |
43 |
Correct |
205 ms |
39552 KB |
Output is correct |
44 |
Execution timed out |
2047 ms |
18104 KB |
Time limit exceeded |
45 |
Halted |
0 ms |
0 KB |
- |