Submission #599109

#	Time	Username	Problem	Language	Result	Execution time	Memory
599109		SlavicG	Event Hopping (BOI22_events)	C++17	25 / 100	712 ms	100440 KiB

events

#include "bits/stdc++.h"
using namespace std;

const int N = 5000;
int dist[N][N];
int l[N], r[N], n, q;
vector<int> events[2 * N + 5];
void go(int start) {
    queue<int> q;
    vector<bool> closed(n, false);
    q.push(start);
    dist[start][start] = 0;
    for(int i = r[start]; i >= 0; --i) {
        while(!q.empty() && closed[q.front()]) q.pop();
        for(int e: events[i]) {
            if(e == start) continue;
            if(e < 0) continue;
            if(!q.empty()) {
                dist[start][e] = dist[start][q.front()] + 1;
                q.push(e);
            }
        }
        for(int e: events[i]) {
            if(e >= 0) continue;
            int idx = -e - 1;
            closed[idx] = true;
        }
    }
}
int main() {
    vector<int> v;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i < n; ++i) {
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
        r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();
        events[r[i]].push_back(i);
        events[l[i]].push_back(-i - 1);
    }
    for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) dist[i][j] = -1;
    for(int i = 0; i < n; ++i) go(i);
    while(q--) {
        int a, b; cin >> a >> b; --a, --b;
        if(dist[b][a] == -1) cout << "impossible\n";
        else cout << dist[b][a] << "\n";
    }
}

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