oj.uz

Submission #714305

# Submission time Handle Problem Language Result Execution time Memory
714305 2023-03-24T08:22:33 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 128356 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<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';
//    }
    int dists[n + 1][n + 1];
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            dists[i][j] = -1;
        }
    }
    bool check[n + 1];
    for(int i = 1;i <= n;++i)check[i] = 0;
    for(int i = 0;i < q;++i){
        int u, v;
        cin >> u >> v;
        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 1587 ms 3704 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.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 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 7 ms 4180 KB Output is correct
6 Correct 12 ms 5044 KB Output is correct
7 Correct 22 ms 5848 KB Output is correct
8 Correct 27 ms 6884 KB Output is correct
9 Correct 10 ms 8288 KB Output is correct

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 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 7 ms 4180 KB Output is correct
6 Correct 12 ms 5044 KB Output is correct
7 Correct 22 ms 5848 KB Output is correct
8 Correct 27 ms 6884 KB Output is correct
9 Correct 10 ms 8288 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 4180 KB Output is correct
13 Correct 7 ms 4180 KB Output is correct
14 Correct 8 ms 4224 KB Output is correct
15 Correct 15 ms 5076 KB Output is correct
16 Correct 24 ms 5784 KB Output is correct
17 Correct 27 ms 6868 KB Output is correct
18 Correct 10 ms 8276 KB Output is correct
19 Execution timed out 1587 ms 128356 KB Time limit exceeded
20 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 7 ms 4180 KB Output is correct
4 Correct 7 ms 4180 KB Output is correct
5 Correct 7 ms 4180 KB Output is correct
6 Correct 12 ms 5044 KB Output is correct
7 Correct 22 ms 5848 KB Output is correct
8 Correct 27 ms 6884 KB Output is correct
9 Correct 10 ms 8288 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 4304 KB Output is correct
13 Correct 7 ms 4308 KB Output is correct
14 Correct 7 ms 4180 KB Output is correct
15 Correct 12 ms 5076 KB Output is correct
16 Correct 22 ms 5844 KB Output is correct
17 Correct 27 ms 6932 KB Output is correct
18 Correct 11 ms 8204 KB Output is correct
19 Execution timed out 1573 ms 3600 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 1560 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 1587 ms 3704 KB Time limit exceeded
3 Halted 0 ms 0 KB -