Submission #604383

#	Time	Username	Problem	Language	Result	Execution time	Memory
604383		Jomnoi	Event Hopping (BOI22_events)	C++17	10 / 100	1593 ms	43172 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];
int dist[MAX_N];
int can_reach[MAX_M][MAX_M];
vector <int> graph[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];
    }

    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';
        }
    }
    return 0;
}

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