Submission #599112

#	Time	Username	Problem	Language	Result	Execution time	Memory
599112		SlavicG	Event Hopping (BOI22_events)	C++17	40 / 100	1577 ms	123040 KiB

events

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

const int N = 1e6 + 10;
int l[N], r[N], n, q;
vector<int> events[N];

vector<int> go(int start) {
    queue<int> q;
    vector<bool> closed(n, false);
    q.push(start);
    vector<int> dist(n, -1);
    dist[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[e] = dist[q.front()] + 1;
                q.push(e);
            }
        }
        for(int e: events[i]) {
            if(e >= 0) continue;
            int idx = -e - 1;
            closed[idx] = true;
        }
    }
    return dist;
}
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);
    }

    if(n <= 5000) {
        vector<vector<int>> dist;
        for(int i = 0; i < n; ++i) dist.push_back(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";
        }
    } else {
        while(q--) {
            int a, b; cin >> a >> b; --a, --b;
            vector<int> dist = go(b);
            if(dist[a] == -1) cout << "impossible\n";
            else cout << dist[a] << "\n";
        }
    }
}

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