Submission #697800

#	Time	Username	Problem	Language	Result	Execution time	Memory
697800		Duy_e	Event Hopping (BOI22_events)	C++14	10 / 100	1594 ms	51876 KiB

events

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 1e5 + 5;

ll n, q, s[N], e[N];
vector <int> cmp, out[2 * N], in[2 * N];
vector <int> d[N];

const ll Nmax = 5005;
int dist[Nmax][Nmax];
void bfs(int st, int *f) {
    rep(i, 1, n) f[i] = 1e9;
    f[st] = 0;
    queue <int> q;
    q.push(st);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int v: d[u]) if (f[v] > f[u] + 1) {
            f[v] = f[u] + 1;
            q.push(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    rep(i, 1, n) {
        cin >> s[i] >> e[i];
        cmp.push_back(s[i]);
        cmp.push_back(e[i]);
    }

    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

    auto find = [&] (ll x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
    };

    rep(i, 1, n) {
        s[i] = find(s[i]);
        e[i] = find(e[i]);
        in[s[i]].push_back(i);
        out[e[i]].push_back(i);
    }

    set <int> save;
    rep(timer, 1, 2 * n) {
        for (int i: in[timer]) save.insert(i);
        for (int i: out[timer]) {
            for (int j: save)
                d[i].push_back(j);
        }

        for (int i: out[timer])
            save.erase(i);
    }

    rep(i, 1, n) bfs(i, dist[i]);

    while (q --) {
        int u, v;
        cin >> u >> v;
        if (dist[u][v] >= (int)1e9)
            cout << "impossible\n";
        else
            cout << dist[u][v] << '\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