oj.uz

답안 #599134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
599134 2022-07-19T10:33:43 Z Vanilla Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199488 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 5e3 + 2;
struct nd {
    int x;
    int y;
    int idx;

    bool operator < (const nd& oth) const {
        return make_pair(x, y) < make_pair(oth.x, oth.y);
    }
} a [maxn];
int dist [maxn][maxn];
vector <int> ad [maxn];

void prec (int u, int x) {
    queue <int> q;
    q.push(u);
    dist[u][x] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v: ad[u]){
            if (dist[u][x] + 1 < dist[v][x]) {
                dist[v][x] = dist[u][x] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) dist[i][j] = 1e9;
        cin >> a[i].x >> a[i].y;
        a[i].idx = i;
    }
    cout << "\n";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (i != j && a[j].x <= a[i].y && a[i].y <= a[j].y) {
                // cout << i << " " << j << "\n";
                ad[i].push_back(j);
            }
        }
    }
    // sort(a, a + n);
    for (int i = 0; i < n; i++){
        prec(i, i);
    }
    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j < n; j++){
    //         cout << i << " " << j << " " << dist[j][i] << "\n";
    //     }
    // }
    while (q--){
        int x,y;
        cin >> x >> y;
        x--, y--;
        cout << (dist[y][x] == 1e9 ? "impossible": to_string(dist[y][x])) << "\n";
    }
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 269 ms 199488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 17 ms 8416 KB Output is correct
4 Correct 14 ms 8424 KB Output is correct
5 Correct 19 ms 8428 KB Output is correct
6 Correct 60 ms 9192 KB Output is correct
7 Correct 179 ms 10000 KB Output is correct
8 Correct 213 ms 11060 KB Output is correct
9 Correct 1410 ms 12408 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 17 ms 8416 KB Output is correct
4 Correct 14 ms 8424 KB Output is correct
5 Correct 19 ms 8428 KB Output is correct
6 Correct 60 ms 9192 KB Output is correct
7 Correct 179 ms 10000 KB Output is correct
8 Correct 213 ms 11060 KB Output is correct
9 Correct 1410 ms 12408 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 17 ms 8428 KB Output is correct
13 Correct 12 ms 8404 KB Output is correct
14 Correct 19 ms 8436 KB Output is correct
15 Correct 70 ms 9192 KB Output is correct
16 Correct 180 ms 9940 KB Output is correct
17 Correct 208 ms 11052 KB Output is correct
18 Correct 1244 ms 12404 KB Output is correct
19 Execution timed out 1592 ms 128228 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 17 ms 8416 KB Output is correct
4 Correct 14 ms 8424 KB Output is correct
5 Correct 19 ms 8428 KB Output is correct
6 Correct 60 ms 9192 KB Output is correct
7 Correct 179 ms 10000 KB Output is correct
8 Correct 213 ms 11060 KB Output is correct
9 Correct 1410 ms 12408 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 17 ms 8404 KB Output is correct
13 Correct 12 ms 8428 KB Output is correct
14 Correct 20 ms 8432 KB Output is correct
15 Correct 58 ms 9196 KB Output is correct
16 Correct 247 ms 9944 KB Output is correct
17 Correct 219 ms 10964 KB Output is correct
18 Correct 1262 ms 12444 KB Output is correct
19 Runtime error 282 ms 199244 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 285 ms 199396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 269 ms 199488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -