oj.uz

Submission #599056

# Submission time Handle Problem Language Result Execution time Memory
599056 2022-07-19T09:35:26 Z SlavicG Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 128276 KB 
#include "bits/stdc++.h"
using namespace std;

const int N = 5001;
int dist[N][N];
vector<int> adj[N];
void bfs(int start) {
    queue<int> q; q.push(start);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v: adj[u]) {
            if(dist[start][v] == -1) {
                dist[start][v] = dist[start][u] + 1;
                q.push(v);
            }
        }
    }
}
int main() {
    for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) dist[i][j] = (i == j ? 0 : -1);
    int n, q; cin >> n >> q;
    vector<int> l(n), r(n);
    for(int i = 0; i < n; ++i) cin >> l[i] >> r[i];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            if(r[i] >= l[j] && r[i] <= r[j]) {
                adj[i].push_back(j);
            }
        }
    }
    for(int i = 0; i < n; ++i) bfs(i);
    while(q--) {
        int a, b; cin >> a >> b; --a, --b;
        if(dist[a][b] == -1) cout << "impossible\n";
        else cout << dist[a][b] << "\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 98208 KB Output is correct
2 Execution timed out 1581 ms 99076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98204 KB Output is correct
2 Correct 54 ms 98260 KB Output is correct
3 Correct 64 ms 98316 KB Output is correct
4 Correct 63 ms 98256 KB Output is correct
5 Correct 74 ms 98316 KB Output is correct
6 Correct 109 ms 99100 KB Output is correct
7 Correct 193 ms 99908 KB Output is correct
8 Correct 225 ms 100984 KB Output is correct
9 Correct 948 ms 102324 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98204 KB Output is correct
2 Correct 54 ms 98260 KB Output is correct
3 Correct 64 ms 98316 KB Output is correct
4 Correct 63 ms 98256 KB Output is correct
5 Correct 74 ms 98316 KB Output is correct
6 Correct 109 ms 99100 KB Output is correct
7 Correct 193 ms 99908 KB Output is correct
8 Correct 225 ms 100984 KB Output is correct
9 Correct 948 ms 102324 KB Output is correct
10 Correct 61 ms 98236 KB Output is correct
11 Correct 62 ms 98256 KB Output is correct
12 Correct 72 ms 98336 KB Output is correct
13 Correct 66 ms 98252 KB Output is correct
14 Correct 70 ms 98252 KB Output is correct
15 Correct 101 ms 99076 KB Output is correct
16 Correct 229 ms 99932 KB Output is correct
17 Correct 240 ms 100980 KB Output is correct
18 Correct 998 ms 102328 KB Output is correct
19 Execution timed out 1568 ms 128276 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98204 KB Output is correct
2 Correct 54 ms 98260 KB Output is correct
3 Correct 64 ms 98316 KB Output is correct
4 Correct 63 ms 98256 KB Output is correct
5 Correct 74 ms 98316 KB Output is correct
6 Correct 109 ms 99100 KB Output is correct
7 Correct 193 ms 99908 KB Output is correct
8 Correct 225 ms 100984 KB Output is correct
9 Correct 948 ms 102324 KB Output is correct
10 Correct 55 ms 98276 KB Output is correct
11 Correct 79 ms 98240 KB Output is correct
12 Correct 71 ms 98252 KB Output is correct
13 Correct 67 ms 98220 KB Output is correct
14 Correct 73 ms 98252 KB Output is correct
15 Correct 101 ms 99116 KB Output is correct
16 Correct 189 ms 99932 KB Output is correct
17 Correct 258 ms 100980 KB Output is correct
18 Correct 1018 ms 102320 KB Output is correct
19 Execution timed out 1596 ms 100780 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 99264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 98208 KB Output is correct
2 Execution timed out 1581 ms 99076 KB Time limit exceeded
3 Halted 0 ms 0 KB -