oj.uz

Submission #745794

# Submission time Handle Problem Language Result Execution time Memory
745794 2023-05-21T07:56:44 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 130732 KB 
#include <iostream>
#include <vector>
using namespace std;

struct event {
    int s, e;
};

int n, q, a, b;
vector <event> v(5001);
vector <vector <int>> g(1e5 + 1);
vector <vector <int>> d(5001, vector <int>(5001, 1e9));
vector <bool> done(5001, false);

void dfs(int x) {
    if (done[x]) return;
    done[x] = true;
    for (int i : g[x]) {
        dfs(i);
        for (int j = 1; j <= n; j++) d[x][j] = min(d[x][j], d[i][j] + 1);
    }
}

int main()
{
    cin >> n >> q;
    if (n > 5000) return 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].s >> v[i].e;
        d[i][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (v[i].e >= v[j].s && v[i].e <= v[j].e) g[i].push_back(j);
        }
    }
    for (int i = 1; i <= n; i++) dfs(i);
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        if (d[a][b] < 1e9) cout << d[a][b] << "\n";
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100684 KB Output is correct
2 Incorrect 39 ms 100716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100684 KB Output is correct
2 Correct 43 ms 100740 KB Output is correct
3 Correct 57 ms 100772 KB Output is correct
4 Correct 61 ms 100684 KB Output is correct
5 Correct 49 ms 100796 KB Output is correct
6 Correct 201 ms 101556 KB Output is correct
7 Correct 408 ms 102364 KB Output is correct
8 Correct 643 ms 103420 KB Output is correct
9 Correct 1135 ms 104816 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100684 KB Output is correct
2 Correct 43 ms 100740 KB Output is correct
3 Correct 57 ms 100772 KB Output is correct
4 Correct 61 ms 100684 KB Output is correct
5 Correct 49 ms 100796 KB Output is correct
6 Correct 201 ms 101556 KB Output is correct
7 Correct 408 ms 102364 KB Output is correct
8 Correct 643 ms 103420 KB Output is correct
9 Correct 1135 ms 104816 KB Output is correct
10 Correct 44 ms 100684 KB Output is correct
11 Correct 43 ms 100680 KB Output is correct
12 Correct 51 ms 100924 KB Output is correct
13 Correct 52 ms 100780 KB Output is correct
14 Correct 52 ms 100684 KB Output is correct
15 Correct 193 ms 101540 KB Output is correct
16 Correct 413 ms 102360 KB Output is correct
17 Correct 554 ms 103424 KB Output is correct
18 Correct 1178 ms 104932 KB Output is correct
19 Execution timed out 1575 ms 130732 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100684 KB Output is correct
2 Correct 43 ms 100740 KB Output is correct
3 Correct 57 ms 100772 KB Output is correct
4 Correct 61 ms 100684 KB Output is correct
5 Correct 49 ms 100796 KB Output is correct
6 Correct 201 ms 101556 KB Output is correct
7 Correct 408 ms 102364 KB Output is correct
8 Correct 643 ms 103420 KB Output is correct
9 Correct 1135 ms 104816 KB Output is correct
10 Correct 42 ms 100692 KB Output is correct
11 Correct 51 ms 100684 KB Output is correct
12 Correct 51 ms 100776 KB Output is correct
13 Correct 59 ms 100684 KB Output is correct
14 Correct 52 ms 100732 KB Output is correct
15 Correct 201 ms 101548 KB Output is correct
16 Correct 386 ms 102364 KB Output is correct
17 Correct 580 ms 103516 KB Output is correct
18 Correct 1047 ms 104928 KB Output is correct
19 Incorrect 52 ms 100788 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 100684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100684 KB Output is correct
2 Incorrect 39 ms 100716 KB Output isn't correct
3 Halted 0 ms 0 KB -