Submission #721580

#	Time	Username	Problem	Language	Result	Execution time	Memory
721580		The_Samurai	Event Hopping (BOI22_events)	C++17	10 / 100	1584 ms	524288 KiB

events

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

struct node {
    int l, r, i;
};

bool comp(node a, node b) {
    if (a.r < b.r) return true;
    if (a.r > b.r) return false;
    return a.l < b.l;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<node> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].i = i + 1;
    }
    sort(a.begin(), a.end(), comp);
    vector<int> ind(n + 1);
    for (int i = 0; i < n; i++) {
        ind[a[i].i] = i;
    }
    vector<vector<int>> can(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[j].l <= a[i].r and a[i].r <= a[j].r) {
                g[i].emplace_back(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        can[i][i] = 0;
        queue<int> pq;
        pq.push(i);
        while (!pq.empty()) {
            int u = pq.front();
            pq.pop();
            for (int v : g[u]) {
                if (can[i][v] == -1) {
                    can[i][v] = can[i][u] + 1;
                    pq.push(v);
                }
            }
        }
    }
    while (q--) {
        int si, ei;
        cin >> si >> ei;
        si = ind[si];
        ei = ind[ei];
        if (can[si][ei] == -1) cout << "impossible";
        else cout << can[si][ei];
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

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