Submission #745980

#	Time	Username	Problem	Language	Result	Execution time	Memory
745980		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	1582 ms	340356 KiB

events

#include <algorithm>
#include <climits>
#include <iostream>
#include <set>
#include <queue>
#include <vector>

using namespace std;

int const INF = INT_MAX / 3;

struct event {
    int s, e, id;
};

enum point_type {
    start,
    end,
};

struct point {
    point_type ty;
    int tm;
    int event_id;
};

vector<int> bfs(vector<vector<int>> const& graph, int const start) {
    queue<int> q;
    q.push(start);

    vector<int> dist(graph.size(), INF);
    dist[start] = 0;

    while (!q.empty()) {
        int const cur = q.front();
        q.pop();

        for (int const& neigh : graph[cur]) {
            if (dist[neigh] != INF) {
                continue;
            }

            dist[neigh] = dist[cur] + 1;
            q.push(neigh);
        }
    }

    return dist;
}

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

    int n, q;
    cin >> n >> q;

    vector<event> events(n);
    vector<point> points;

    for (int i = 0; i < n; i++) {
        cin >> events[i].s >> events[i].e;
        events[i].id = i;

        points.push_back({ point_type::start, events[i].s, i });
        points.push_back({ point_type::end, events[i].e, i });
    }
    
    sort(points.begin(), points.end(), [](auto const& a, auto const& b) {
        return a.tm < b.tm || (a.tm == b.tm && a.ty == point_type::start);
    });

    vector<vector<int>> graph(n);

    {
        set<int> cur;
        vector<int> removed;
        int last_tm = -1;

        for (auto const& [ty, tm, e_id] : points) {
            if (tm > last_tm) {
                for (int const& r : removed) {
                    cur.erase(r);
                }

                removed.clear();
            }

            if (ty == point_type::start) {
                cur.insert(e_id);
            }
            else {
                removed.push_back(e_id);
                
                for (int const& c : cur) {
                    graph[e_id].push_back(c);
                }
            }
        }
    }

    vector<vector<int>> dist(n);

    for (int i = 0; i < n; i++) {
        dist[i] = bfs(graph, i);
    }

    while (q--) {
        int s, e;
        cin >> s >> e;
        s--; e--;

        if (dist[s][e] == INF) {
            cout << "impossible\n";
        }
        else {
            cout << dist[s][e] << "\n";
        }
    }
}

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