oj.uz

Submission #599109

# Submission time Handle Problem Language Result Execution time Memory
599109 2022-07-19T10:13:44 Z SlavicG Event Hopping (BOI22_events) C++17
25 / 100
 712 ms 100440 KB 
#include "bits/stdc++.h"
using namespace std;

const int N = 5000;
int dist[N][N];
int l[N], r[N], n, q;
vector<int> events[2 * N + 5];
void go(int start) {
    queue<int> q;
    vector<bool> closed(n, false);
    q.push(start);
    dist[start][start] = 0;
    for(int i = r[start]; i >= 0; --i) {
        while(!q.empty() && closed[q.front()]) q.pop();
        for(int e: events[i]) {
            if(e == start) continue;
            if(e < 0) continue;
            if(!q.empty()) {
                dist[start][e] = dist[start][q.front()] + 1;
                q.push(e);
            }
        }
        for(int e: events[i]) {
            if(e >= 0) continue;
            int idx = -e - 1;
            closed[idx] = true;
        }
    }
}
int main() {
    vector<int> v;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i < n; ++i) {
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
        r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();
        events[r[i]].push_back(i);
        events[l[i]].push_back(-i - 1);
    }
    for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) dist[i][j] = -1;
    for(int i = 0; i < n; ++i) go(i);
    while(q--) {
        int a, b; cin >> a >> b; --a, --b;
        if(dist[b][a] == -1) cout << "impossible\n";
        else cout << dist[b][a] << "\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98252 KB Output is correct
2 Runtime error 95 ms 5708 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98304 KB Output is correct
2 Correct 39 ms 98356 KB Output is correct
3 Correct 46 ms 98372 KB Output is correct
4 Correct 55 ms 98336 KB Output is correct
5 Correct 52 ms 98420 KB Output is correct
6 Correct 47 ms 98388 KB Output is correct
7 Correct 59 ms 98472 KB Output is correct
8 Correct 59 ms 98356 KB Output is correct
9 Correct 47 ms 98388 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98304 KB Output is correct
2 Correct 39 ms 98356 KB Output is correct
3 Correct 46 ms 98372 KB Output is correct
4 Correct 55 ms 98336 KB Output is correct
5 Correct 52 ms 98420 KB Output is correct
6 Correct 47 ms 98388 KB Output is correct
7 Correct 59 ms 98472 KB Output is correct
8 Correct 59 ms 98356 KB Output is correct
9 Correct 47 ms 98388 KB Output is correct
10 Correct 36 ms 98304 KB Output is correct
11 Correct 35 ms 98288 KB Output is correct
12 Correct 47 ms 98380 KB Output is correct
13 Correct 46 ms 98436 KB Output is correct
14 Correct 48 ms 98380 KB Output is correct
15 Correct 45 ms 98508 KB Output is correct
16 Correct 59 ms 98384 KB Output is correct
17 Correct 55 ms 98428 KB Output is correct
18 Correct 51 ms 98412 KB Output is correct
19 Correct 484 ms 100184 KB Output is correct
20 Correct 464 ms 100104 KB Output is correct
21 Correct 485 ms 100376 KB Output is correct
22 Correct 419 ms 100404 KB Output is correct
23 Correct 712 ms 100368 KB Output is correct
24 Correct 699 ms 100440 KB Output is correct
25 Correct 499 ms 100128 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98304 KB Output is correct
2 Correct 39 ms 98356 KB Output is correct
3 Correct 46 ms 98372 KB Output is correct
4 Correct 55 ms 98336 KB Output is correct
5 Correct 52 ms 98420 KB Output is correct
6 Correct 47 ms 98388 KB Output is correct
7 Correct 59 ms 98472 KB Output is correct
8 Correct 59 ms 98356 KB Output is correct
9 Correct 47 ms 98388 KB Output is correct
10 Correct 39 ms 98252 KB Output is correct
11 Correct 37 ms 98384 KB Output is correct
12 Correct 48 ms 98356 KB Output is correct
13 Correct 46 ms 98420 KB Output is correct
14 Correct 49 ms 98364 KB Output is correct
15 Correct 46 ms 98432 KB Output is correct
16 Correct 54 ms 98368 KB Output is correct
17 Correct 55 ms 98476 KB Output is correct
18 Correct 55 ms 98380 KB Output is correct
19 Runtime error 90 ms 5528 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 5784 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98252 KB Output is correct
2 Runtime error 95 ms 5708 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -