oj.uz

Submission #604464

# Submission time Handle Problem Language Result Execution time Memory
604464 2022-07-25T06:45:04 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 772 ms 14640 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; l++) {
            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 2 ms 2644 KB Output is correct
2 Incorrect 65 ms 13268 KB Output isn't correct
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 18 ms 10592 KB Output is correct
4 Correct 13 ms 10580 KB Output is correct
5 Correct 18 ms 10572 KB Output is correct
6 Correct 49 ms 11372 KB Output is correct
7 Correct 143 ms 12264 KB Output is correct
8 Correct 148 ms 13256 KB Output is correct
9 Correct 746 ms 14548 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 18 ms 10592 KB Output is correct
4 Correct 13 ms 10580 KB Output is correct
5 Correct 18 ms 10572 KB Output is correct
6 Correct 49 ms 11372 KB Output is correct
7 Correct 143 ms 12264 KB Output is correct
8 Correct 148 ms 13256 KB Output is correct
9 Correct 746 ms 14548 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 17 ms 10572 KB Output is correct
13 Correct 15 ms 10664 KB Output is correct
14 Correct 18 ms 10580 KB Output is correct
15 Correct 48 ms 11336 KB Output is correct
16 Correct 123 ms 12240 KB Output is correct
17 Correct 139 ms 13288 KB Output is correct
18 Correct 772 ms 14628 KB Output is correct
19 Incorrect 35 ms 5136 KB Output isn't correct
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 18 ms 10592 KB Output is correct
4 Correct 13 ms 10580 KB Output is correct
5 Correct 18 ms 10572 KB Output is correct
6 Correct 49 ms 11372 KB Output is correct
7 Correct 143 ms 12264 KB Output is correct
8 Correct 148 ms 13256 KB Output is correct
9 Correct 746 ms 14548 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 17 ms 10692 KB Output is correct
13 Correct 16 ms 10580 KB Output is correct
14 Correct 20 ms 10652 KB Output is correct
15 Correct 49 ms 11452 KB Output is correct
16 Correct 117 ms 12228 KB Output is correct
17 Correct 141 ms 13280 KB Output is correct
18 Correct 763 ms 14640 KB Output is correct
19 Incorrect 42 ms 12288 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 13216 KB Output isn't correct
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 Incorrect 65 ms 13268 KB Output isn't correct
3 Halted 0 ms 0 KB -