oj.uz

답안 #745804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745804 2023-05-21T08:04:35 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 130772 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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 100684 KB Output is correct
2 Incorrect 47 ms 100652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 100660 KB Output is correct
2 Correct 41 ms 100684 KB Output is correct
3 Correct 48 ms 100776 KB Output is correct
4 Correct 52 ms 100744 KB Output is correct
5 Correct 53 ms 100708 KB Output is correct
6 Correct 214 ms 101544 KB Output is correct
7 Correct 418 ms 102296 KB Output is correct
8 Correct 692 ms 103332 KB Output is correct
9 Correct 1226 ms 104840 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 100660 KB Output is correct
2 Correct 41 ms 100684 KB Output is correct
3 Correct 48 ms 100776 KB Output is correct
4 Correct 52 ms 100744 KB Output is correct
5 Correct 53 ms 100708 KB Output is correct
6 Correct 214 ms 101544 KB Output is correct
7 Correct 418 ms 102296 KB Output is correct
8 Correct 692 ms 103332 KB Output is correct
9 Correct 1226 ms 104840 KB Output is correct
10 Correct 49 ms 100688 KB Output is correct
11 Correct 63 ms 100656 KB Output is correct
12 Correct 54 ms 100760 KB Output is correct
13 Correct 58 ms 100716 KB Output is correct
14 Correct 52 ms 100784 KB Output is correct
15 Correct 265 ms 101524 KB Output is correct
16 Correct 444 ms 102308 KB Output is correct
17 Correct 592 ms 103356 KB Output is correct
18 Correct 1404 ms 104908 KB Output is correct
19 Execution timed out 1562 ms 130772 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 100660 KB Output is correct
2 Correct 41 ms 100684 KB Output is correct
3 Correct 48 ms 100776 KB Output is correct
4 Correct 52 ms 100744 KB Output is correct
5 Correct 53 ms 100708 KB Output is correct
6 Correct 214 ms 101544 KB Output is correct
7 Correct 418 ms 102296 KB Output is correct
8 Correct 692 ms 103332 KB Output is correct
9 Correct 1226 ms 104840 KB Output is correct
10 Correct 55 ms 100768 KB Output is correct
11 Correct 41 ms 100692 KB Output is correct
12 Correct 56 ms 100792 KB Output is correct
13 Correct 49 ms 100736 KB Output is correct
14 Correct 58 ms 100768 KB Output is correct
15 Correct 199 ms 101576 KB Output is correct
16 Correct 470 ms 102324 KB Output is correct
17 Correct 624 ms 103436 KB Output is correct
18 Correct 1146 ms 104928 KB Output is correct
19 Incorrect 48 ms 100712 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 100684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 100684 KB Output is correct
2 Incorrect 47 ms 100652 KB Output isn't correct
3 Halted 0 ms 0 KB -