#include <iostream>
#include <vector>
using namespace std;
struct event {
int s, e;
};
int n, q, a, b;
vector <event> v(5001);
vector <vector <int>> g(1e5 + 1);
vector <vector <int>> d(5001, vector <int>(5001, 1e9));
vector <bool> done(5001, false);
void dfs(int x) {
if (done[x]) return;
done[x] = true;
for (int i : g[x]) {
dfs(i);
for (int j = 1; j <= n; j++) d[x][j] = min(d[x][j], d[i][j] + 1);
}
}
int main()
{
cin >> n >> q;
if (n > 5000) return 0;
for (int i = 1; i <= n; i++) {
cin >> v[i].s >> v[i].e;
d[i][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (v[i].e >= v[j].s && v[i].e <= v[j].e) g[i].push_back(j);
}
}
for (int i = 1; i <= n; i++) dfs(i);
for (int i = 0; i < q; i++) {
cin >> a >> b;
if (d[a][b] < 1e9) cout << d[a][b] << "\n";
else cout << "impossible\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
100684 KB |
Output is correct |
2 |
Incorrect |
39 ms |
100716 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
100684 KB |
Output is correct |
2 |
Correct |
43 ms |
100740 KB |
Output is correct |
3 |
Correct |
57 ms |
100772 KB |
Output is correct |
4 |
Correct |
61 ms |
100684 KB |
Output is correct |
5 |
Correct |
49 ms |
100796 KB |
Output is correct |
6 |
Correct |
201 ms |
101556 KB |
Output is correct |
7 |
Correct |
408 ms |
102364 KB |
Output is correct |
8 |
Correct |
643 ms |
103420 KB |
Output is correct |
9 |
Correct |
1135 ms |
104816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
100684 KB |
Output is correct |
2 |
Correct |
43 ms |
100740 KB |
Output is correct |
3 |
Correct |
57 ms |
100772 KB |
Output is correct |
4 |
Correct |
61 ms |
100684 KB |
Output is correct |
5 |
Correct |
49 ms |
100796 KB |
Output is correct |
6 |
Correct |
201 ms |
101556 KB |
Output is correct |
7 |
Correct |
408 ms |
102364 KB |
Output is correct |
8 |
Correct |
643 ms |
103420 KB |
Output is correct |
9 |
Correct |
1135 ms |
104816 KB |
Output is correct |
10 |
Correct |
44 ms |
100684 KB |
Output is correct |
11 |
Correct |
43 ms |
100680 KB |
Output is correct |
12 |
Correct |
51 ms |
100924 KB |
Output is correct |
13 |
Correct |
52 ms |
100780 KB |
Output is correct |
14 |
Correct |
52 ms |
100684 KB |
Output is correct |
15 |
Correct |
193 ms |
101540 KB |
Output is correct |
16 |
Correct |
413 ms |
102360 KB |
Output is correct |
17 |
Correct |
554 ms |
103424 KB |
Output is correct |
18 |
Correct |
1178 ms |
104932 KB |
Output is correct |
19 |
Execution timed out |
1575 ms |
130732 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
100684 KB |
Output is correct |
2 |
Correct |
43 ms |
100740 KB |
Output is correct |
3 |
Correct |
57 ms |
100772 KB |
Output is correct |
4 |
Correct |
61 ms |
100684 KB |
Output is correct |
5 |
Correct |
49 ms |
100796 KB |
Output is correct |
6 |
Correct |
201 ms |
101556 KB |
Output is correct |
7 |
Correct |
408 ms |
102364 KB |
Output is correct |
8 |
Correct |
643 ms |
103420 KB |
Output is correct |
9 |
Correct |
1135 ms |
104816 KB |
Output is correct |
10 |
Correct |
42 ms |
100692 KB |
Output is correct |
11 |
Correct |
51 ms |
100684 KB |
Output is correct |
12 |
Correct |
51 ms |
100776 KB |
Output is correct |
13 |
Correct |
59 ms |
100684 KB |
Output is correct |
14 |
Correct |
52 ms |
100732 KB |
Output is correct |
15 |
Correct |
201 ms |
101548 KB |
Output is correct |
16 |
Correct |
386 ms |
102364 KB |
Output is correct |
17 |
Correct |
580 ms |
103516 KB |
Output is correct |
18 |
Correct |
1047 ms |
104928 KB |
Output is correct |
19 |
Incorrect |
52 ms |
100788 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
44 ms |
100684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
100684 KB |
Output is correct |
2 |
Incorrect |
39 ms |
100716 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |