oj.uz

Submission #599069

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

const int N = 5000;
int dist[N][N];
int l[N], r[N];
void go(set<pair<int, int>> s, int start) {
    queue<int> q;
    q.push(start);
    dist[start][start] = 0;
    s.erase({r[start], start});
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        while(!s.empty()) {
            auto it = s.upper_bound({l[u], -1});
            if(it == s.end()) break;
            if(it->first > r[u]) break;
            dist[start][it->second] = dist[start][u] + 1;
            q.push(it->second);
            s.erase(it);
        }
    }
}
int main() {
    int n, q; cin >> n >> q;
    for(int i = 0; i < n; ++i) cin >> l[i] >> r[i];
    set<pair<int, int>> s;
    for(int i = 0; i < n; ++i) s.insert({r[i], i});
    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(s, 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 35 ms 98052 KB Output is correct
2 Execution timed out 1578 ms 107468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 98124 KB Output is correct
2 Correct 36 ms 98056 KB Output is correct
3 Correct 106 ms 98232 KB Output is correct
4 Correct 102 ms 98236 KB Output is correct
5 Correct 109 ms 98244 KB Output is correct
6 Correct 95 ms 98124 KB Output is correct
7 Correct 101 ms 98240 KB Output is correct
8 Correct 97 ms 98240 KB Output is correct
9 Correct 122 ms 98236 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 98124 KB Output is correct
2 Correct 36 ms 98056 KB Output is correct
3 Correct 106 ms 98232 KB Output is correct
4 Correct 102 ms 98236 KB Output is correct
5 Correct 109 ms 98244 KB Output is correct
6 Correct 95 ms 98124 KB Output is correct
7 Correct 101 ms 98240 KB Output is correct
8 Correct 97 ms 98240 KB Output is correct
9 Correct 122 ms 98236 KB Output is correct
10 Correct 37 ms 98044 KB Output is correct
11 Correct 38 ms 98028 KB Output is correct
12 Correct 110 ms 98236 KB Output is correct
13 Correct 99 ms 98112 KB Output is correct
14 Correct 109 ms 98292 KB Output is correct
15 Correct 90 ms 98204 KB Output is correct
16 Correct 98 ms 98244 KB Output is correct
17 Correct 93 ms 98240 KB Output is correct
18 Correct 123 ms 98236 KB Output is correct
19 Execution timed out 1596 ms 98628 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 98124 KB Output is correct
2 Correct 36 ms 98056 KB Output is correct
3 Correct 106 ms 98232 KB Output is correct
4 Correct 102 ms 98236 KB Output is correct
5 Correct 109 ms 98244 KB Output is correct
6 Correct 95 ms 98124 KB Output is correct
7 Correct 101 ms 98240 KB Output is correct
8 Correct 97 ms 98240 KB Output is correct
9 Correct 122 ms 98236 KB Output is correct
10 Correct 37 ms 98040 KB Output is correct
11 Correct 41 ms 98036 KB Output is correct
12 Correct 102 ms 98204 KB Output is correct
13 Correct 88 ms 98236 KB Output is correct
14 Correct 104 ms 98240 KB Output is correct
15 Correct 90 ms 98192 KB Output is correct
16 Correct 100 ms 98268 KB Output is correct
17 Correct 96 ms 98216 KB Output is correct
18 Correct 118 ms 98240 KB Output is correct
19 Execution timed out 1579 ms 107588 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 1553 ms 107524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98052 KB Output is correct
2 Execution timed out 1578 ms 107468 KB Time limit exceeded
3 Halted 0 ms 0 KB -