oj.uz

Submission #572942

# Submission time Handle Problem Language Result Execution time Memory
572942 2022-06-05T14:30:31 Z MohamedFaresNebili Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 58612 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);
                }
            }
            vector<ii> query[N + 1]; int ans[Q];
            for(int l = 0; l < Q; l++) {
                int U, V; cin >> U >> V;
                query[U].pb({V, l});
            }
            for(int U = 1; U <= N; U++) {
                if(!query[U].size()) continue;
                vector<int> D(N + 1, -1);
                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] != -1) continue;
                        D[u] = D[A] + 1; q.push(u);
                    }
                }
                for(auto V : query[U])
                    ans[V.ss] = D[V.ff];
            }
            for(int l = 0; l < Q; l++) {
                if(ans[l] == -1) cout << "impossible\n";
                else cout << ans[l] << "\n";
            }
        }

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 6 ms 2724 KB Output is correct
6 Correct 13 ms 4376 KB Output is correct
7 Correct 20 ms 5980 KB Output is correct
8 Correct 22 ms 8020 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 6 ms 2724 KB Output is correct
6 Correct 13 ms 4376 KB Output is correct
7 Correct 20 ms 5980 KB Output is correct
8 Correct 22 ms 8020 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 6 ms 2644 KB Output is correct
13 Correct 6 ms 2772 KB Output is correct
14 Correct 7 ms 2644 KB Output is correct
15 Correct 11 ms 4308 KB Output is correct
16 Correct 20 ms 5980 KB Output is correct
17 Correct 23 ms 7992 KB Output is correct
18 Correct 9 ms 10684 KB Output is correct
19 Execution timed out 1580 ms 58612 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 6 ms 2724 KB Output is correct
6 Correct 13 ms 4376 KB Output is correct
7 Correct 20 ms 5980 KB Output is correct
8 Correct 22 ms 8020 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 5 ms 2644 KB Output is correct
13 Correct 6 ms 2644 KB Output is correct
14 Correct 6 ms 2644 KB Output is correct
15 Correct 11 ms 4240 KB Output is correct
16 Correct 19 ms 5972 KB Output is correct
17 Correct 25 ms 8140 KB Output is correct
18 Correct 10 ms 10708 KB Output is correct
19 Execution timed out 1593 ms 4404 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 1586 ms 4428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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