oj.uz

Submission #599135

# Submission time Handle Problem Language Result Execution time Memory
599135 2022-07-19T10:35:02 Z Vanilla Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199472 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) {
    set <int> q;
    // queue <int> q;
    q.insert(u);
    dist[u][x] = 0;
    while (!q.empty()) {
        int u = *q.begin();
        q.erase(q.begin());
        for (int v: ad[u]){
            if (dist[u][x] + 1 < dist[v][x]) {
                dist[v][x] = dist[u][x] + 1;
                q.insert(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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 315 ms 199340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 31 ms 8424 KB Output is correct
4 Correct 18 ms 8428 KB Output is correct
5 Correct 33 ms 8408 KB Output is correct
6 Correct 92 ms 9216 KB Output is correct
7 Correct 249 ms 10060 KB Output is correct
8 Correct 291 ms 11092 KB Output is correct
9 Correct 1401 ms 12460 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 31 ms 8424 KB Output is correct
4 Correct 18 ms 8428 KB Output is correct
5 Correct 33 ms 8408 KB Output is correct
6 Correct 92 ms 9216 KB Output is correct
7 Correct 249 ms 10060 KB Output is correct
8 Correct 291 ms 11092 KB Output is correct
9 Correct 1401 ms 12460 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 31 ms 8404 KB Output is correct
13 Correct 17 ms 8408 KB Output is correct
14 Correct 33 ms 8420 KB Output is correct
15 Correct 109 ms 9204 KB Output is correct
16 Correct 261 ms 10040 KB Output is correct
17 Correct 282 ms 11100 KB Output is correct
18 Correct 1388 ms 12452 KB Output is correct
19 Execution timed out 1586 ms 128312 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 31 ms 8424 KB Output is correct
4 Correct 18 ms 8428 KB Output is correct
5 Correct 33 ms 8408 KB Output is correct
6 Correct 92 ms 9216 KB Output is correct
7 Correct 249 ms 10060 KB Output is correct
8 Correct 291 ms 11092 KB Output is correct
9 Correct 1401 ms 12460 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 29 ms 8436 KB Output is correct
13 Correct 17 ms 8436 KB Output is correct
14 Correct 34 ms 8408 KB Output is correct
15 Correct 105 ms 9292 KB Output is correct
16 Correct 254 ms 10036 KB Output is correct
17 Correct 264 ms 11084 KB Output is correct
18 Correct 1374 ms 12452 KB Output is correct
19 Runtime error 290 ms 199472 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 351 ms 199240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 315 ms 199340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -