oj.uz

Submission #604463

# Submission time Handle Problem Language Result Execution time Memory
604463 2022-07-25T06:44:26 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 14688 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 < vec[r].second) {
                r++;
            }

            if(r < N) {
                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], S[s])) - vec.begin();
            int pe = lower_bound(vec.begin(), vec.end(), make_pair(E[e], S[e])) - 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 1597 ms 4572 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 17 ms 10592 KB Output is correct
4 Correct 12 ms 10580 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11456 KB Output is correct
7 Correct 151 ms 12148 KB Output is correct
8 Correct 143 ms 13252 KB Output is correct
9 Correct 744 ms 14688 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 17 ms 10592 KB Output is correct
4 Correct 12 ms 10580 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11456 KB Output is correct
7 Correct 151 ms 12148 KB Output is correct
8 Correct 143 ms 13252 KB Output is correct
9 Correct 744 ms 14688 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 17 ms 10684 KB Output is correct
13 Correct 13 ms 10692 KB Output is correct
14 Correct 18 ms 10696 KB Output is correct
15 Correct 48 ms 11404 KB Output is correct
16 Correct 146 ms 12204 KB Output is correct
17 Correct 137 ms 13264 KB Output is correct
18 Correct 792 ms 14644 KB Output is correct
19 Runtime error 1465 ms 5512 KB Execution killed with signal 11
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 17 ms 10592 KB Output is correct
4 Correct 12 ms 10580 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11456 KB Output is correct
7 Correct 151 ms 12148 KB Output is correct
8 Correct 143 ms 13252 KB Output is correct
9 Correct 744 ms 14688 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 18 ms 10580 KB Output is correct
13 Correct 15 ms 10624 KB Output is correct
14 Correct 21 ms 10580 KB Output is correct
15 Correct 47 ms 11328 KB Output is correct
16 Correct 119 ms 12236 KB Output is correct
17 Correct 143 ms 13228 KB Output is correct
18 Correct 734 ms 14636 KB Output is correct
19 Execution timed out 1508 ms 8612 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 1581 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 1597 ms 4572 KB Time limit exceeded
3 Halted 0 ms 0 KB -