oj.uz

Submission #745816

# Submission time Handle Problem Language Result Execution time Memory
745816 2023-05-21T08:15:19 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 130640 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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 (i == j) continue;
            if (v[i].e >= v[j].s && v[i].e < v[j].e) g[i].push_back(j);
            if (v[i].e == v[j].e) d[i][j] = 1;
        }
    }
    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";
    }

    /*cout << endl;
    for (int i = 1; i <= n; i++) {
        cout << endl;
        for (int j = 1; j <= n; j++) {
            cout << d[i][j] << " ";
        }
    }*/
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100700 KB Output is correct
2 Incorrect 43 ms 100736 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 40 ms 100684 KB Output is correct
2 Correct 41 ms 100676 KB Output is correct
3 Correct 47 ms 100768 KB Output is correct
4 Correct 50 ms 100704 KB Output is correct
5 Correct 49 ms 100756 KB Output is correct
6 Correct 196 ms 101512 KB Output is correct
7 Correct 395 ms 102348 KB Output is correct
8 Correct 637 ms 103500 KB Output is correct
9 Correct 48 ms 100764 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100684 KB Output is correct
2 Correct 41 ms 100676 KB Output is correct
3 Correct 47 ms 100768 KB Output is correct
4 Correct 50 ms 100704 KB Output is correct
5 Correct 49 ms 100756 KB Output is correct
6 Correct 196 ms 101512 KB Output is correct
7 Correct 395 ms 102348 KB Output is correct
8 Correct 637 ms 103500 KB Output is correct
9 Correct 48 ms 100764 KB Output is correct
10 Correct 43 ms 100696 KB Output is correct
11 Correct 48 ms 100644 KB Output is correct
12 Correct 51 ms 100776 KB Output is correct
13 Correct 55 ms 100976 KB Output is correct
14 Correct 51 ms 100796 KB Output is correct
15 Correct 194 ms 101452 KB Output is correct
16 Correct 420 ms 102604 KB Output is correct
17 Correct 607 ms 103372 KB Output is correct
18 Correct 49 ms 100772 KB Output is correct
19 Execution timed out 1580 ms 130640 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100684 KB Output is correct
2 Correct 41 ms 100676 KB Output is correct
3 Correct 47 ms 100768 KB Output is correct
4 Correct 50 ms 100704 KB Output is correct
5 Correct 49 ms 100756 KB Output is correct
6 Correct 196 ms 101512 KB Output is correct
7 Correct 395 ms 102348 KB Output is correct
8 Correct 637 ms 103500 KB Output is correct
9 Correct 48 ms 100764 KB Output is correct
10 Correct 42 ms 100664 KB Output is correct
11 Correct 51 ms 100716 KB Output is correct
12 Correct 50 ms 100788 KB Output is correct
13 Correct 49 ms 100748 KB Output is correct
14 Correct 49 ms 100732 KB Output is correct
15 Correct 200 ms 101552 KB Output is correct
16 Correct 377 ms 102336 KB Output is correct
17 Correct 581 ms 103388 KB Output is correct
18 Correct 57 ms 100668 KB Output is correct
19 Incorrect 44 ms 100668 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100700 KB Output is correct
2 Incorrect 43 ms 100736 KB Output isn't correct
3 Halted 0 ms 0 KB -