oj.uz

Submission #880417

# Submission time Handle Problem Language Result Execution time Memory
880417 2023-11-29T11:48:34 Z VectorLi Toll (BOI17_toll) C++14
100 / 100
 209 ms 85760 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

const int V = 50000, K = 16;
const int N = 5;
const int MAX = numeric_limits<int>::max();

struct Element {
    int a[N][N];
    int* operator [] (int i) {
        return a[i];
    }
    Element() {
        for (int i = 0; i < N; i++) {
            fill(a[i], a[i] + N, MAX);
            a[i][i] = 0;
        }
    }
};

Element operator + (Element &u, Element &v) {
    Element w;
    for (int i = 0; i < N; i++) {
        fill(w[i], w[i] + N, MAX);
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (u[i][k] < MAX && v[k][j] < MAX) {
                    w[i][j] = min(w[i][j], u[i][k] + v[k][j]);
                }
            }
        }
    }
    return w;
}

void print(Element u) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << u[i][j] << " ";
        }
        cout << "\n";
    }
}

int n, m, k, q;
vector<pair<int, int>> e[V];
Element f[K][V];

void solve() {
    cin >> k >> n >> m >> q;
    for (int u = 0; u < n / k; u++) {
        for (int i = 0; i < N; i++) {
            fill(f[0][u][i], f[0][u][i] + N, MAX);
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        int w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        f[0][u / k][u % k][v % k] = w;
    }

    for (int i = 0; i < K - 1; i++) {
       for (int u = 0; u < n / k; u++) {
            if (u + (1 << i) >= n / k) {
                f[i + 1][u] = f[i][u];
            } else {
                f[i + 1][u] = f[i][u] + f[i][u + (1 << i)];
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        int p = u / k;
        Element x;
        for (int j = K - 1; j >= 0; j--) {
            if (p + (1 << j) <= v / k) {
                x = x + f[j][p];
                p = p + (1 << j);
            }
        }
        if (x[u % k][v % k] < MAX) {
            cout << x[u % k][v % k] << "\n";
        } else {
            cout << -1 << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 82516 KB Output is correct
2 Correct 18 ms 79708 KB Output is correct
3 Correct 17 ms 79704 KB Output is correct
4 Correct 18 ms 79708 KB Output is correct
5 Correct 21 ms 79960 KB Output is correct
6 Correct 22 ms 79704 KB Output is correct
7 Correct 21 ms 79944 KB Output is correct
8 Correct 209 ms 82380 KB Output is correct
9 Correct 180 ms 82252 KB Output is correct
10 Correct 175 ms 79956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 83236 KB Output is correct
2 Correct 18 ms 79704 KB Output is correct
3 Correct 18 ms 79708 KB Output is correct
4 Correct 18 ms 79704 KB Output is correct
5 Correct 18 ms 79708 KB Output is correct
6 Correct 22 ms 79700 KB Output is correct
7 Correct 32 ms 79964 KB Output is correct
8 Correct 35 ms 79952 KB Output is correct
9 Correct 195 ms 82324 KB Output is correct
10 Correct 121 ms 84612 KB Output is correct
11 Correct 133 ms 82980 KB Output is correct
12 Correct 117 ms 82524 KB Output is correct
13 Correct 80 ms 84816 KB Output is correct
14 Correct 77 ms 83028 KB Output is correct
15 Correct 63 ms 82260 KB Output is correct
16 Correct 65 ms 82408 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 79704 KB Output is correct
2 Correct 21 ms 79708 KB Output is correct
3 Correct 22 ms 79728 KB Output is correct
4 Correct 18 ms 79704 KB Output is correct
5 Correct 18 ms 79692 KB Output is correct
6 Correct 19 ms 79708 KB Output is correct
7 Correct 19 ms 79964 KB Output is correct
8 Correct 20 ms 80004 KB Output is correct
9 Correct 19 ms 79964 KB Output is correct
10 Correct 167 ms 82252 KB Output is correct
11 Correct 117 ms 82768 KB Output is correct
12 Correct 101 ms 84424 KB Output is correct
13 Correct 115 ms 85048 KB Output is correct
14 Correct 99 ms 83548 KB Output is correct
15 Correct 58 ms 82256 KB Output is correct
16 Correct 57 ms 82260 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 79704 KB Output is correct
2 Correct 21 ms 79708 KB Output is correct
3 Correct 22 ms 79728 KB Output is correct
4 Correct 18 ms 79704 KB Output is correct
5 Correct 18 ms 79692 KB Output is correct
6 Correct 19 ms 79708 KB Output is correct
7 Correct 19 ms 79964 KB Output is correct
8 Correct 20 ms 80004 KB Output is correct
9 Correct 19 ms 79964 KB Output is correct
10 Correct 167 ms 82252 KB Output is correct
11 Correct 117 ms 82768 KB Output is correct
12 Correct 101 ms 84424 KB Output is correct
13 Correct 115 ms 85048 KB Output is correct
14 Correct 99 ms 83548 KB Output is correct
15 Correct 58 ms 82256 KB Output is correct
16 Correct 57 ms 82260 KB Output is correct
17 Correct 130 ms 83004 KB Output is correct
18 Correct 18 ms 79708 KB Output is correct
19 Correct 17 ms 79708 KB Output is correct
20 Correct 18 ms 79708 KB Output is correct
21 Correct 18 ms 79708 KB Output is correct
22 Correct 20 ms 79964 KB Output is correct
23 Correct 24 ms 79964 KB Output is correct
24 Correct 25 ms 79912 KB Output is correct
25 Correct 23 ms 79992 KB Output is correct
26 Correct 22 ms 79960 KB Output is correct
27 Correct 174 ms 82512 KB Output is correct
28 Correct 123 ms 84820 KB Output is correct
29 Correct 108 ms 85028 KB Output is correct
30 Correct 105 ms 83748 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 82516 KB Output is correct
2 Correct 18 ms 79708 KB Output is correct
3 Correct 17 ms 79704 KB Output is correct
4 Correct 18 ms 79708 KB Output is correct
5 Correct 21 ms 79960 KB Output is correct
6 Correct 22 ms 79704 KB Output is correct
7 Correct 21 ms 79944 KB Output is correct
8 Correct 209 ms 82380 KB Output is correct
9 Correct 180 ms 82252 KB Output is correct
10 Correct 175 ms 79956 KB Output is correct
11 Correct 137 ms 83236 KB Output is correct
12 Correct 18 ms 79704 KB Output is correct
13 Correct 18 ms 79708 KB Output is correct
14 Correct 18 ms 79704 KB Output is correct
15 Correct 18 ms 79708 KB Output is correct
16 Correct 22 ms 79700 KB Output is correct
17 Correct 32 ms 79964 KB Output is correct
18 Correct 35 ms 79952 KB Output is correct
19 Correct 195 ms 82324 KB Output is correct
20 Correct 121 ms 84612 KB Output is correct
21 Correct 133 ms 82980 KB Output is correct
22 Correct 117 ms 82524 KB Output is correct
23 Correct 80 ms 84816 KB Output is correct
24 Correct 77 ms 83028 KB Output is correct
25 Correct 63 ms 82260 KB Output is correct
26 Correct 65 ms 82408 KB Output is correct
27 Correct 18 ms 79704 KB Output is correct
28 Correct 21 ms 79708 KB Output is correct
29 Correct 22 ms 79728 KB Output is correct
30 Correct 18 ms 79704 KB Output is correct
31 Correct 18 ms 79692 KB Output is correct
32 Correct 19 ms 79708 KB Output is correct
33 Correct 19 ms 79964 KB Output is correct
34 Correct 20 ms 80004 KB Output is correct
35 Correct 19 ms 79964 KB Output is correct
36 Correct 167 ms 82252 KB Output is correct
37 Correct 117 ms 82768 KB Output is correct
38 Correct 101 ms 84424 KB Output is correct
39 Correct 115 ms 85048 KB Output is correct
40 Correct 99 ms 83548 KB Output is correct
41 Correct 58 ms 82256 KB Output is correct
42 Correct 57 ms 82260 KB Output is correct
43 Correct 130 ms 83004 KB Output is correct
44 Correct 18 ms 79708 KB Output is correct
45 Correct 17 ms 79708 KB Output is correct
46 Correct 18 ms 79708 KB Output is correct
47 Correct 18 ms 79708 KB Output is correct
48 Correct 20 ms 79964 KB Output is correct
49 Correct 24 ms 79964 KB Output is correct
50 Correct 25 ms 79912 KB Output is correct
51 Correct 23 ms 79992 KB Output is correct
52 Correct 22 ms 79960 KB Output is correct
53 Correct 174 ms 82512 KB Output is correct
54 Correct 123 ms 84820 KB Output is correct
55 Correct 108 ms 85028 KB Output is correct
56 Correct 105 ms 83748 KB Output is correct
57 Correct 121 ms 85760 KB Output is correct
58 Correct 198 ms 82360 KB Output is correct
59 Correct 134 ms 83028 KB Output is correct