oj.uz

Submission #754088

# Submission time Handle Problem Language Result Execution time Memory
754088 2023-06-06T16:50:45 Z jakobrs Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 11116 KB 
#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});
    }

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

    for (auto point : points) {
        if (point.type == 0) {
            current.insert(point.idx);
        } else {
            current.erase(point.idx);
            nexts[point.idx].insert(nexts[point.idx].end(), current.begin(),
                                    current.end());
        }
    }

    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);

        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1559 ms 11116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Incorrect 8 ms 1484 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Incorrect 8 ms 1484 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Incorrect 8 ms 1484 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 11112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1559 ms 11116 KB Time limit exceeded
3 Halted 0 ms 0 KB -