oj.uz

Submission #604459

# Submission time Handle Problem Language Result Execution time Memory
604459 2022-07-25T06:43:03 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 14668 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 <= 1000 and Q <= 100) {
        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 1514 ms 8600 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 18 ms 10572 KB Output is correct
4 Correct 12 ms 10628 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 125 ms 12260 KB Output is correct
8 Correct 161 ms 13200 KB Output is correct
9 Correct 779 ms 14668 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 18 ms 10572 KB Output is correct
4 Correct 12 ms 10628 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 125 ms 12260 KB Output is correct
8 Correct 161 ms 13200 KB Output is correct
9 Correct 779 ms 14668 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 19 ms 10580 KB Output is correct
13 Correct 15 ms 10660 KB Output is correct
14 Correct 19 ms 10576 KB Output is correct
15 Correct 48 ms 11348 KB Output is correct
16 Correct 165 ms 12172 KB Output is correct
17 Correct 154 ms 13292 KB Output is correct
18 Correct 875 ms 14660 KB Output is correct
19 Execution timed out 1574 ms 2772 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 18 ms 10572 KB Output is correct
4 Correct 12 ms 10628 KB Output is correct
5 Correct 20 ms 10580 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 125 ms 12260 KB Output is correct
8 Correct 161 ms 13200 KB Output is correct
9 Correct 779 ms 14668 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 18 ms 10688 KB Output is correct
13 Correct 13 ms 10580 KB Output is correct
14 Correct 21 ms 10580 KB Output is correct
15 Correct 56 ms 11412 KB Output is correct
16 Correct 132 ms 12248 KB Output is correct
17 Correct 171 ms 13296 KB Output is correct
18 Correct 1010 ms 14652 KB Output is correct
19 Execution timed out 1574 ms 4496 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 1522 ms 4564 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 1514 ms 8600 KB Time limit exceeded
3 Halted 0 ms 0 KB -