Submission #721674

#	Time	Username	Problem	Language	Result	Execution time	Memory
721674		kas_s	Event Hopping (BOI22_events)	C++17	10 / 100	1577 ms	366848 KiB

events

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;


int N;
vector<vector<int>> adj;
int bfs(int start, int end) {
    vector<int> dist(N + 1);
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        for (int &v: adj[curr]) {
            if (dist[v]) continue;
            dist[v] = dist[curr] + 1;
            q.push(v);
        }
    }
    return dist[end];
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int Q;
    cin >> N >> Q;
    adj.resize(N + 1);
    vector<pair<int, int>> ranges(N);
    set<int> unique;
    for (auto &v: ranges){
        cin >> v.first >> v.second;
        unique.insert(v.first);
        unique.insert(v.second);
    }
    map<int, int> compress;
    int idx = 1;
    for (auto &v: unique) {
        compress[v] = idx++;
    }
    vector<vector<int>> start(unique.size() + 1), end(unique.size() + 1);
    for (int i = 0; i < N; i++) {
        ranges[i].first = compress[ranges[i].first];
        ranges[i].second = compress[ranges[i].second];
        start[ranges[i].first].push_back(i+1);
        end[ranges[i].second].push_back(i+1);
    }
    set<int> running;
    for (int i = 1; i <= (int)unique.size(); i++) {
        for (auto &v: start[i]) {
            running.insert(v);
        }
        for (auto &v: end[i]) {
            for (auto &u: running) {
                if (v == u) continue;
                adj[v].push_back(u);
            }
        }
        for (auto &v: end[i]) {
            running.erase(v);
        }
    }
    while (Q--) {
        int s, e;
        cin >> s >> e;
        if (s == e) {
            cout << "0\n";
            continue;
        }
        int res = bfs(s, e);
        if (res == 0) {
            cout << "impossible\n";
        } else {
            cout << res << '\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