oj.uz

Submission #599112

# Submission time Handle Problem Language Result Execution time Memory
599112 2022-07-19T10:17:59 Z SlavicG Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 123040 KB 
#include "bits/stdc++.h"
using namespace std;

const int N = 1e6 + 10;
int l[N], r[N], n, q;
vector<int> events[N];

vector<int> go(int start) {
    queue<int> q;
    vector<bool> closed(n, false);
    q.push(start);
    vector<int> dist(n, -1);
    dist[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[e] = dist[q.front()] + 1;
                q.push(e);
            }
        }
        for(int e: events[i]) {
            if(e >= 0) continue;
            int idx = -e - 1;
            closed[idx] = true;
        }
    }
    return dist;
}
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);
    }

    if(n <= 5000) {
        vector<vector<int>> dist;
        for(int i = 0; i < n; ++i) dist.push_back(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";
        }
    } else {
        while(q--) {
            int a, b; cin >> a >> b; --a, --b;
            vector<int> dist = go(b);
            if(dist[a] == -1) cout << "impossible\n";
            else cout << dist[a] << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23748 KB Output is correct
2 Execution timed out 1577 ms 29260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 23 ms 27732 KB Output is correct
4 Correct 24 ms 27732 KB Output is correct
5 Correct 24 ms 27700 KB Output is correct
6 Correct 23 ms 27784 KB Output is correct
7 Correct 32 ms 27772 KB Output is correct
8 Correct 30 ms 27828 KB Output is correct
9 Correct 24 ms 27776 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 23 ms 27732 KB Output is correct
4 Correct 24 ms 27732 KB Output is correct
5 Correct 24 ms 27700 KB Output is correct
6 Correct 23 ms 27784 KB Output is correct
7 Correct 32 ms 27772 KB Output is correct
8 Correct 30 ms 27828 KB Output is correct
9 Correct 24 ms 27776 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 24 ms 27732 KB Output is correct
13 Correct 25 ms 27752 KB Output is correct
14 Correct 23 ms 27732 KB Output is correct
15 Correct 23 ms 27788 KB Output is correct
16 Correct 34 ms 27772 KB Output is correct
17 Correct 30 ms 27732 KB Output is correct
18 Correct 24 ms 27768 KB Output is correct
19 Correct 456 ms 122704 KB Output is correct
20 Correct 464 ms 122572 KB Output is correct
21 Correct 462 ms 122848 KB Output is correct
22 Correct 461 ms 123040 KB Output is correct
23 Correct 753 ms 123024 KB Output is correct
24 Correct 716 ms 122896 KB Output is correct
25 Correct 514 ms 122560 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 23 ms 27732 KB Output is correct
4 Correct 24 ms 27732 KB Output is correct
5 Correct 24 ms 27700 KB Output is correct
6 Correct 23 ms 27784 KB Output is correct
7 Correct 32 ms 27772 KB Output is correct
8 Correct 30 ms 27828 KB Output is correct
9 Correct 24 ms 27776 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 24 ms 27688 KB Output is correct
13 Correct 22 ms 27748 KB Output is correct
14 Correct 24 ms 27812 KB Output is correct
15 Correct 24 ms 27748 KB Output is correct
16 Correct 32 ms 27720 KB Output is correct
17 Correct 31 ms 27732 KB Output is correct
18 Correct 25 ms 27788 KB Output is correct
19 Correct 553 ms 29224 KB Output is correct
20 Correct 286 ms 30400 KB Output is correct
21 Correct 265 ms 31080 KB Output is correct
22 Correct 304 ms 32176 KB Output is correct
23 Correct 913 ms 34296 KB Output is correct
24 Correct 990 ms 34236 KB Output is correct
25 Correct 168 ms 28224 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23748 KB Output is correct
2 Execution timed out 1577 ms 29260 KB Time limit exceeded
3 Halted 0 ms 0 KB -