oj.uz

답안 #745980

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745980 2023-05-21T10:19:14 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 340356 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();
            }

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1582 ms 340356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 11 ms 4300 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 11 ms 4308 KB Output is correct
6 Incorrect 43 ms 5152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 11 ms 4300 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 11 ms 4308 KB Output is correct
6 Incorrect 43 ms 5152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 11 ms 4300 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 11 ms 4308 KB Output is correct
6 Incorrect 43 ms 5152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1550 ms 300540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1582 ms 340356 KB Time limit exceeded
3 Halted 0 ms 0 KB -