oj.uz

Submission #572894

# Submission time Handle Problem Language Result Execution time Memory
572894 2022-06-05T12:40:17 Z MohamedFaresNebili Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 57356 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define int ll

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int N, Q; int S[100001], E[100001];
        vector<int> adj[100001];

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> Q;
            for(int l = 1; l <= N; l++)
                cin >> S[l] >> E[l];
            for(int l = 1; l <= N; l++) {
                for(int i = 1; i <= N; i++) {
                    if(l == i) continue;
                    if(E[l] >= S[i] && E[l] <= E[i])
                        adj[l].pb(i);
                }
            }
            while(Q--) {
                int U, V; cin >> U >> V;
                vector<int> D(N + 1, 1e9 + 7);
                queue<int> q; q.push(U); D[U] = 0;
                while(!q.empty()) {
                    int A = q.front(); q.pop();
                    for(auto u : adj[A]) {
                        if(D[u] != 1e9 + 7) continue;
                        D[u] = D[A] + 1; q.push(u);
                    }
                }
                if(D[V] ==  1e9 + 7) cout << "impossible\n";
                else cout << D[V] << "\n";
            }
        }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Execution timed out 1565 ms 6648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 7 ms 2744 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 7 ms 2744 KB Output is correct
6 Correct 15 ms 4328 KB Output is correct
7 Correct 27 ms 5972 KB Output is correct
8 Correct 33 ms 8048 KB Output is correct
9 Correct 133 ms 10708 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 7 ms 2744 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 7 ms 2744 KB Output is correct
6 Correct 15 ms 4328 KB Output is correct
7 Correct 27 ms 5972 KB Output is correct
8 Correct 33 ms 8048 KB Output is correct
9 Correct 133 ms 10708 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 7 ms 2656 KB Output is correct
13 Correct 7 ms 2712 KB Output is correct
14 Correct 8 ms 2644 KB Output is correct
15 Correct 12 ms 4308 KB Output is correct
16 Correct 25 ms 5912 KB Output is correct
17 Correct 29 ms 7948 KB Output is correct
18 Correct 147 ms 10744 KB Output is correct
19 Execution timed out 1577 ms 57356 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 7 ms 2744 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 7 ms 2744 KB Output is correct
6 Correct 15 ms 4328 KB Output is correct
7 Correct 27 ms 5972 KB Output is correct
8 Correct 33 ms 8048 KB Output is correct
9 Correct 133 ms 10708 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 9 ms 2712 KB Output is correct
13 Correct 6 ms 2644 KB Output is correct
14 Correct 8 ms 2644 KB Output is correct
15 Correct 12 ms 4308 KB Output is correct
16 Correct 28 ms 5964 KB Output is correct
17 Correct 27 ms 8020 KB Output is correct
18 Correct 139 ms 10708 KB Output is correct
19 Execution timed out 1555 ms 6368 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 1561 ms 6800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Execution timed out 1565 ms 6648 KB Time limit exceeded
3 Halted 0 ms 0 KB -