oj.uz

Submission #746011

# Submission time Handle Problem Language Result Execution time Memory
746011 2023-05-21T10:33:45 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 9716 KB 
#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();
            }

            last_tm = tm;

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

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

        auto const dist = bfs(graph, s);

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 1184 KB Output is correct
7 Correct 17 ms 2020 KB Output is correct
8 Correct 21 ms 3000 KB Output is correct
9 Runtime error 3 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 1184 KB Output is correct
7 Correct 17 ms 2020 KB Output is correct
8 Correct 21 ms 3000 KB Output is correct
9 Runtime error 3 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 1184 KB Output is correct
7 Correct 17 ms 2020 KB Output is correct
8 Correct 21 ms 3000 KB Output is correct
9 Runtime error 3 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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