oj.uz

Submission #599077

# Submission time Handle Problem Language Result Execution time Memory
599077 2022-07-19T09:54:39 Z SlavicG Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 107752 KB 
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 37 ms 98124 KB Output is correct
2 Execution timed out 1568 ms 107616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98124 KB Output is correct
2 Correct 36 ms 98076 KB Output is correct
3 Correct 100 ms 98236 KB Output is correct
4 Correct 90 ms 98236 KB Output is correct
5 Correct 101 ms 98132 KB Output is correct
6 Correct 89 ms 98236 KB Output is correct
7 Correct 97 ms 98240 KB Output is correct
8 Correct 91 ms 98124 KB Output is correct
9 Correct 115 ms 98240 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98124 KB Output is correct
2 Correct 36 ms 98076 KB Output is correct
3 Correct 100 ms 98236 KB Output is correct
4 Correct 90 ms 98236 KB Output is correct
5 Correct 101 ms 98132 KB Output is correct
6 Correct 89 ms 98236 KB Output is correct
7 Correct 97 ms 98240 KB Output is correct
8 Correct 91 ms 98124 KB Output is correct
9 Correct 115 ms 98240 KB Output is correct
10 Correct 37 ms 98128 KB Output is correct
11 Correct 37 ms 98080 KB Output is correct
12 Correct 104 ms 98144 KB Output is correct
13 Correct 88 ms 98236 KB Output is correct
14 Correct 104 ms 98360 KB Output is correct
15 Correct 89 ms 98132 KB Output is correct
16 Correct 97 ms 98236 KB Output is correct
17 Correct 93 ms 98124 KB Output is correct
18 Correct 115 ms 98240 KB Output is correct
19 Execution timed out 1583 ms 98596 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98124 KB Output is correct
2 Correct 36 ms 98076 KB Output is correct
3 Correct 100 ms 98236 KB Output is correct
4 Correct 90 ms 98236 KB Output is correct
5 Correct 101 ms 98132 KB Output is correct
6 Correct 89 ms 98236 KB Output is correct
7 Correct 97 ms 98240 KB Output is correct
8 Correct 91 ms 98124 KB Output is correct
9 Correct 115 ms 98240 KB Output is correct
10 Correct 36 ms 98060 KB Output is correct
11 Correct 45 ms 98080 KB Output is correct
12 Correct 108 ms 98296 KB Output is correct
13 Correct 92 ms 98140 KB Output is correct
14 Correct 111 ms 98236 KB Output is correct
15 Correct 123 ms 98240 KB Output is correct
16 Correct 124 ms 98180 KB Output is correct
17 Correct 92 ms 98132 KB Output is correct
18 Correct 116 ms 98240 KB Output is correct
19 Execution timed out 1587 ms 107752 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 1577 ms 107656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98124 KB Output is correct
2 Execution timed out 1568 ms 107616 KB Time limit exceeded
3 Halted 0 ms 0 KB -