Submission #754092

#	Time	Username	Problem	Language	Result	Execution time	Memory
754092		jakobrs	Event Hopping (BOI22_events)	C++17	10 / 100	1596 ms	403136 KiB

events

#include <algorithm>
#include <iostream>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>

using i64 = int64_t;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    i64 n, q;
    std::cin >> n >> q;

    struct Point {
        i64 time;
        int type;
        int idx;

        bool operator<(const Point &rhs) const {
            return std::tie(time, type, idx) <
                   std::tie(rhs.time, rhs.type, rhs.idx);
        }
    };

    std::vector<std::vector<i64>> nexts(n);
    std::unordered_set<i64> current;
    std::vector<Point> points;

    for (int i = 0; i < n; i++) {
        i64 s, e;
        std::cin >> s >> e;

        points.push_back(Point{.time = s, .type = 0, .idx = i});
        points.push_back(Point{.time = e, .type = 1, .idx = i});
        points.push_back(Point{.time = e, .type = 2, .idx = i});
    }

    std::sort(points.begin(), points.end());

    for (auto point : points) {
        switch (point.type) {
            case 0:
                current.insert(point.idx);
                break;
            case 1:
                nexts[point.idx].insert(nexts[point.idx].end(), current.begin(),
                                        current.end());
                break;
            case 2:
                current.erase(point.idx);
                break;
        }
    }

    std::vector<bool> visited(n);
    std::vector<i64> next;
    std::vector<i64> more;
    for (i64 i = 0; i < q; i++) {
        int s, e;
        std::cin >> s >> e;
        s--, e--;

        std::fill(visited.begin(), visited.end(), false);
        next.clear();
        more.clear();
        next.push_back(s);
        visited[s] = true;

        for (i64 time = 0; !next.empty(); time++) {
            for (i64 node : next) {
                if (node == e) {
                    std::cout << time << '\n';

                    goto next;
                }

                for (i64 possible : nexts[node]) {
                    if (!visited[possible]) {
                        visited[possible] = true;
                        more.push_back(possible);
                    }
                }
            }

            std::swap(next, more);
            more.clear();
        }

        std::cout << "impossible\n";
    next:;
    }
}

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