Submission #604360

#	Time	Username	Problem	Language	Result	Execution time	Memory
604360		Jomnoi	Event Hopping (BOI22_events)	C++17	0 / 100	46 ms	3856 KiB

events

#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], id[MAX_N], p[MAX_N];
int can_reach[MAX_M][MAX_M];
int dp[MAX_N];

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];
    }

    iota(id + 1, id + N + 1, 1);
    sort(id + 1, id + N + 1, [&](const int &a, const int &b) {
        return S[a] < S[b];
    });

    for(int i = 1; i <= N; i++) {
        p[id[i]] = i;
    }

    if(N <= 1000 and Q <= 100) {
        while(Q--) {
            int s, e;
            cin >> s >> e;

            for(int i = 1; i <= N; i++) {
                dp[i] = INF;
            }
            dp[p[s]] = 0;

            for(int i = p[s]; i <= p[e]; i++) {
                for(int j = i + 1; j <= p[e]; j++) {
                    int u = id[i], v = id[j];
                    if(S[v] <= E[u] and E[u] <= E[v]) {
                        dp[v] = min(dp[v], dp[u] + 1);
                    }
                }
            }
            
            if(dp[p[e]] == INF) {
                cout << "impossible\n";
            }
            else {
                cout << dp[p[e]] << '\n';
            }
        }
    }
    else if(N <= 5000) {
        memset(can_reach, -1, sizeof(can_reach));

        for(int i = 1; i <= N; i++) {
            can_reach[id[i]][id[i]] = 0;
            priority_queue <pair <int, int>> pq;
            pq.emplace(0, id[i]);
            for(int j = i + 1; j <= N; j++) {
                while(!pq.empty() and E[pq.top().second] < S[id[j]]) {
                    pq.pop();
                }

                if(!pq.empty()) {
                    can_reach[id[i]][id[j]] = -pq.top().first + 1;
                    pq.emplace(-can_reach[id[i]][id[j]], id[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 if(Q <= 100) {
        while(Q--) {
            int s, e;
            cin >> s >> e;

            dp[p[e]] = -1;
            dp[p[s]] = 0;
            priority_queue <pair <int, int>> pq;
            pq.emplace(0, p[s]);
            for(int i = p[s] + 1; i <= p[e]; i++) {
                while(!pq.empty() and E[pq.top().second] < S[id[i]]) {
                    pq.pop();
                }

                if(!pq.empty()) {
                    dp[id[i]] = -pq.top().first + 1;
                    pq.emplace(-dp[id[i]], id[i]);
                }
            }

            if(dp[p[e]] == -1) {
                cout << "impossible\n";
            }
            else {
                cout << dp[p[e]] << '\n';
            }
        }
    }
    else {
        while(Q--) {
            int s, e;
            cin >> s >> e;

            if(s == e) {
                cout << "0\n";
            }
            else if(S[p[e]] <= E[p[s]] and E[p[s]] <= E[p[e]]) {
                cout << "1\n";
            }
            else {
                cout << "impossible\n";
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30