oj.uz

Submission #604458

# Submission time Handle Problem Language Result Execution time Memory
604458 2022-07-25T06:42:27 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 43056 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 5005;
const int INF = 1e9 + 7;

int S[MAX_N], E[MAX_N];
int dist[MAX_N];
int can_reach[MAX_M][MAX_M];
vector <int> graph[MAX_N];
int nxt[MAX_N][20];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;

    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> E[i];
    }

    if(N <= 5000) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(i != j and S[j] <= E[i] and E[i] <= E[j]) {
                    graph[i].push_back(j);
                }
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                dist[j] = -1;
            }

            queue <int> q;
            q.push(i);
            dist[i] = 0;
            while(!q.empty()) {
                int u = q.front();
                q.pop();

                for(auto v : graph[u]) {
                    if(dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }

            for(int j = 1; j <= N; j++) {
                can_reach[i][j] = dist[j];
            }
        }

        while(Q--) {
            int s, e;
            cin >> s >> e;

            if(can_reach[s][e] == -1) {
                cout << "impossible\n";
            }
            else {
                cout << can_reach[s][e] << '\n';
            }
        }
    }
    else {
        vector <pair <int, int>> vec;
        for(int i = 1; i <= N; i++) {
            vec.emplace_back(E[i], S[i]);
        }

        sort(vec.begin(), vec.end());

        for(int l = 0, r = 0; l < N; r++) {
            while(r < N and vec[l].first < S[r]) {
                r++;
            }

            nxt[l][0] = r;
        }
        for(int j = 1; j < 20; j++) {
            for(int i = 0; i < N; i++) {
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
            }
        }

        while(Q--) {
            int s, e;
            cin >> s >> e;

            int ps = lower_bound(vec.begin(), vec.end(), make_pair(e, s)) - vec.begin();
            int pe = lower_bound(vec.begin(), vec.end(), make_pair(e, s)) - vec.begin();

            int ans = 0;
            for(int i = 19; i >= 0; i--) {
                if(nxt[ps][i] <= pe) {
                    ps = nxt[ps][i];
                    ans += (1<<i);
                }
            }
        
            if(ps == pe) {
                cout << ans << '\n';
            }
            else {
                cout << "impossible\n";
            }
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Execution timed out 1549 ms 8608 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 2 ms 2644 KB Output is correct
3 Correct 16 ms 10644 KB Output is correct
4 Correct 14 ms 10672 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 56 ms 11384 KB Output is correct
7 Correct 141 ms 12212 KB Output is correct
8 Correct 138 ms 13240 KB Output is correct
9 Correct 746 ms 14720 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 2 ms 2644 KB Output is correct
3 Correct 16 ms 10644 KB Output is correct
4 Correct 14 ms 10672 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 56 ms 11384 KB Output is correct
7 Correct 141 ms 12212 KB Output is correct
8 Correct 138 ms 13240 KB Output is correct
9 Correct 746 ms 14720 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 16 ms 10580 KB Output is correct
13 Correct 14 ms 10576 KB Output is correct
14 Correct 21 ms 10676 KB Output is correct
15 Correct 47 ms 11396 KB Output is correct
16 Correct 126 ms 12140 KB Output is correct
17 Correct 151 ms 13228 KB Output is correct
18 Correct 763 ms 14652 KB Output is correct
19 Execution timed out 1561 ms 43056 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 2 ms 2644 KB Output is correct
3 Correct 16 ms 10644 KB Output is correct
4 Correct 14 ms 10672 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 56 ms 11384 KB Output is correct
7 Correct 141 ms 12212 KB Output is correct
8 Correct 138 ms 13240 KB Output is correct
9 Correct 746 ms 14720 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 19 ms 10640 KB Output is correct
13 Correct 15 ms 10584 KB Output is correct
14 Correct 19 ms 10584 KB Output is correct
15 Correct 47 ms 11360 KB Output is correct
16 Correct 120 ms 12208 KB Output is correct
17 Correct 155 ms 13356 KB Output is correct
18 Correct 754 ms 14668 KB Output is correct
19 Runtime error 1500 ms 8596 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1537 ms 8604 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 1549 ms 8608 KB Time limit exceeded
3 Halted 0 ms 0 KB -