Submission #721597

#	Time	Username	Problem	Language	Result	Execution time	Memory
721597		dxz05	Event Hopping (BOI22_events)	C++17	10 / 100	1593 ms	350924 KiB

events

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

vector<int> g[N];
int n;
int d[N];

void bfs(int x){
    fill(d, d + n, 1e9);
    d[x] = 0;
    queue<int> q;
    q.push(x);
    while (!q.empty()){
        x = q.front();
        q.pop();
        for (int y : g[x]){
            if (d[y] == 1e9){
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
}


void solve(){
    int q;
    cin >> n >> q;

    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> perm(n);
    iota(all(perm), 0);

    sort(all(perm), [&](int i, int j){
        return r[i] > r[j];
    });

    set<pair<int, int>> ls;
    for (int i : perm){
        while (!ls.empty() && ls.rbegin()->first > r[i]){
            ls.erase(*ls.rbegin());
        }

        for (auto [_l, j] : ls){
            if (l[j] <= r[i] && r[i] <= r[j]){
                g[i].push_back(j);
            }
            if (l[i] <= r[j] && r[j] <= r[i]){
                g[j].push_back(i);
            }
        }

        ls.emplace(l[i], i);
    }

    for (int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        --x, --y;
        bfs(x);
        if (d[y] == 1e9){
            cout << "impossible" << endl;
        } else {
            cout << d[y] << endl;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    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