oj.uz

Submission #714239

# Submission time Handle Problem Language Result Execution time Memory
714239 2023-03-24T06:55:37 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 130200 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, q;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    vector<int>g[n + 1];
    pair<int, int>events[n + 1];
    for(int i = 1;i <= n;++i){
        cin >> events[i].first >> events[i].second;
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            if(i == j)continue;
            if(events[i].second >= events[j].first && events[i].second <= events[j].second){
                g[i].push_back(j);
            }
        }
    }
//    for(int i = 1;i <= n;++i){
//        cout << i << ": ";
//        for(int j : g[i]){
//            cout << j << " ";
//        }
//        cout << '\n';
//    }
    vector<pair<int, int>>queries;
    while(q--){
        int u, v;
        cin >> u >> v;
        queries.push_back({u, v});
    }
    vector<vector<int>>dists(n + 1, vector<int>(n + 1, -1));
    bool check[n + 1];
    for(int i = 1;i <= n;++i)check[i] = 0;
    for(pair<int, int>query: queries){
        int u = query.first, v = query.second;
        if(dists[u][v] != -1)cout << dists[u][v] << '\n';
        else if(dists[u][v] == -1 && check[u])cout << "impossible\n";
        else{
            queue<int>que;
            que.push(u);
            check[u] = 1;
            dists[u][u] = 0;
            while(!que.empty()){
                int cur = que.front();
                que.pop();
                for(int vv : g[cur]){
                    if(dists[u][vv] == -1){
                        dists[u][vv] = dists[u][cur] + 1;
                        que.push(vv);
                    }
                }
            }
            if(dists[u][v] == -1)cout << "impossible\n";
            else cout << dists[u][v] << '\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 1575 ms 3596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 7 ms 4308 KB Output is correct
6 Correct 12 ms 5076 KB Output is correct
7 Correct 24 ms 5844 KB Output is correct
8 Correct 27 ms 6900 KB Output is correct
9 Correct 8 ms 8276 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 7 ms 4308 KB Output is correct
6 Correct 12 ms 5076 KB Output is correct
7 Correct 24 ms 5844 KB Output is correct
8 Correct 27 ms 6900 KB Output is correct
9 Correct 8 ms 8276 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 4340 KB Output is correct
13 Correct 7 ms 4212 KB Output is correct
14 Correct 8 ms 4308 KB Output is correct
15 Correct 12 ms 5076 KB Output is correct
16 Correct 23 ms 5900 KB Output is correct
17 Correct 26 ms 6896 KB Output is correct
18 Correct 9 ms 8276 KB Output is correct
19 Execution timed out 1579 ms 130200 KB Time limit exceeded
20 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 0 ms 212 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 7 ms 4308 KB Output is correct
5 Correct 7 ms 4308 KB Output is correct
6 Correct 12 ms 5076 KB Output is correct
7 Correct 24 ms 5844 KB Output is correct
8 Correct 27 ms 6900 KB Output is correct
9 Correct 8 ms 8276 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 4320 KB Output is correct
13 Correct 6 ms 4308 KB Output is correct
14 Correct 8 ms 4308 KB Output is correct
15 Correct 12 ms 4992 KB Output is correct
16 Correct 23 ms 5856 KB Output is correct
17 Correct 26 ms 6868 KB Output is correct
18 Correct 9 ms 8276 KB Output is correct
19 Execution timed out 1582 ms 3592 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 3608 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 1575 ms 3596 KB Time limit exceeded
3 Halted 0 ms 0 KB -