oj.uz

Submission #646207

# Submission time Handle Problem Language Result Execution time Memory
646207 2022-09-29T07:43:46 Z retarddestroyer Toll (BOI17_toll) C++14
100 / 100
 229 ms 38984 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fors(u, n, s) for(ll u = (s); u<(n); u++)
#define foru(u, n) fors(u, n, 0)

#define N 50000
#define K 5

struct funny_matrix{ /// element i, j is cost of going from i to j
    ll arr[K][K];

    void id_max(){
        foru(i, K) foru(j, K) arr[i][j]=INT_MAX;
    }

    void id_diag(){
        foru(i, K) foru(j, K) arr[i][j]=INT_MAX;
        foru(i, K) arr[i][i]=0;
    }
};

funny_matrix multiply(funny_matrix a, funny_matrix b){ ///going throug a than b
    funny_matrix output;
    output.id_max();

    foru(i, K) foru(j, K){
        foru(k, K){
            output.arr[i][j] = min(output.arr[i][j], a.arr[i][k] + b.arr[k][j]);
        }
    }

    return output;
}

funny_matrix edges[N];

struct seg_tree{
    funny_matrix arr[4*N];

    void construct_ins(int id, int a, int b){ ///a to b inclusive
        if(a==b) {arr[id] = edges[a]; return;}
        int m = (a+b)/2;
        construct_ins(2*id, a, m); construct_ins(2*id+1, m+1, b);
        arr[id] = multiply(arr[2*id], arr[2*id+1]);
    }

    void construct(){
        construct_ins(1, 0, N-1);
    }

    funny_matrix read_ins(int id, int a, int b, int qa, int qb){
        if (a==qa && b==qb) return arr[id];
        int m = (a+b)/2;
        funny_matrix res1;
        funny_matrix res2;
        res1.id_diag(); res2.id_diag();
        if(qa>qb) {cout << "AAAAAA" << endl;}
        if(qa<=m) res1 = read_ins(2*id, a, m, qa, min(qb, m));
        if(qb>=m+1) res2 = read_ins(2*id+1, m+1, b, max(qa, m+1), qb);
        return multiply(res1, res2);
    }

    funny_matrix read(int qa, int qb){
        return read_ins(1, 0, N-1, qa, qb);
    }
};

seg_tree tree;

int main()
{
    int k; int n; int m; int o;

    cin >> k >> n >> m >> o;

    foru(i, N) edges[i].id_max();

    foru(_i, m){
        ll a, b, t; cin >> a >> b >> t;
        int l = a/k;
        int a_prim = a%k;
        int b_prim = b%k;
        edges[l].arr[a_prim][b_prim] = min(edges[l].arr[a_prim][b_prim], t);
    }

    tree.construct();

    foru(_i, o){
        int a, b; cin >> a >> b;
        int la = a/k; int lb = b/k;
        int a_prim = a%k; int b_prim = b%k;

        if(la==lb){
            if(a_prim==b_prim) cout << 0 << endl;
            else cout << -1 << endl;
            continue;
        }

        if(la>lb){
            cout << -1 << endl;
            continue;
        }

        ll res = tree.read(la, lb-1).arr[a_prim][b_prim];
        if(res>=INT_MAX) cout << -1 << endl;
        else cout << res << endl;
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 35796 KB Output is correct
2 Correct 22 ms 35676 KB Output is correct
3 Correct 24 ms 35700 KB Output is correct
4 Correct 22 ms 35656 KB Output is correct
5 Correct 33 ms 35728 KB Output is correct
6 Correct 30 ms 35732 KB Output is correct
7 Correct 27 ms 35656 KB Output is correct
8 Correct 127 ms 36588 KB Output is correct
9 Correct 126 ms 36552 KB Output is correct
10 Correct 92 ms 35860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35680 KB Output is correct
2 Correct 21 ms 35668 KB Output is correct
3 Correct 25 ms 35716 KB Output is correct
4 Correct 22 ms 35680 KB Output is correct
5 Correct 23 ms 35688 KB Output is correct
6 Correct 22 ms 35680 KB Output is correct
7 Correct 63 ms 35816 KB Output is correct
8 Correct 64 ms 35880 KB Output is correct
9 Correct 108 ms 36568 KB Output is correct
10 Correct 167 ms 37968 KB Output is correct
11 Correct 137 ms 37392 KB Output is correct
12 Correct 117 ms 36940 KB Output is correct
13 Correct 136 ms 38088 KB Output is correct
14 Correct 104 ms 37324 KB Output is correct
15 Correct 86 ms 36948 KB Output is correct
16 Correct 86 ms 36944 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35668 KB Output is correct
2 Correct 21 ms 35744 KB Output is correct
3 Correct 22 ms 35636 KB Output is correct
4 Correct 22 ms 35684 KB Output is correct
5 Correct 22 ms 35744 KB Output is correct
6 Correct 27 ms 35772 KB Output is correct
7 Correct 26 ms 35700 KB Output is correct
8 Correct 28 ms 35740 KB Output is correct
9 Correct 24 ms 35744 KB Output is correct
10 Correct 60 ms 36532 KB Output is correct
11 Correct 95 ms 37204 KB Output is correct
12 Correct 120 ms 37832 KB Output is correct
13 Correct 126 ms 38088 KB Output is correct
14 Correct 110 ms 37572 KB Output is correct
15 Correct 76 ms 36808 KB Output is correct
16 Correct 74 ms 36824 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35668 KB Output is correct
2 Correct 21 ms 35744 KB Output is correct
3 Correct 22 ms 35636 KB Output is correct
4 Correct 22 ms 35684 KB Output is correct
5 Correct 22 ms 35744 KB Output is correct
6 Correct 27 ms 35772 KB Output is correct
7 Correct 26 ms 35700 KB Output is correct
8 Correct 28 ms 35740 KB Output is correct
9 Correct 24 ms 35744 KB Output is correct
10 Correct 60 ms 36532 KB Output is correct
11 Correct 95 ms 37204 KB Output is correct
12 Correct 120 ms 37832 KB Output is correct
13 Correct 126 ms 38088 KB Output is correct
14 Correct 110 ms 37572 KB Output is correct
15 Correct 76 ms 36808 KB Output is correct
16 Correct 74 ms 36824 KB Output is correct
17 Correct 112 ms 37316 KB Output is correct
18 Correct 21 ms 35680 KB Output is correct
19 Correct 22 ms 35644 KB Output is correct
20 Correct 22 ms 35656 KB Output is correct
21 Correct 23 ms 35652 KB Output is correct
22 Correct 25 ms 35740 KB Output is correct
23 Correct 38 ms 35680 KB Output is correct
24 Correct 39 ms 35700 KB Output is correct
25 Correct 41 ms 35700 KB Output is correct
26 Correct 39 ms 35760 KB Output is correct
27 Correct 84 ms 36536 KB Output is correct
28 Correct 147 ms 37960 KB Output is correct
29 Correct 156 ms 38212 KB Output is correct
30 Correct 122 ms 37588 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 35796 KB Output is correct
2 Correct 22 ms 35676 KB Output is correct
3 Correct 24 ms 35700 KB Output is correct
4 Correct 22 ms 35656 KB Output is correct
5 Correct 33 ms 35728 KB Output is correct
6 Correct 30 ms 35732 KB Output is correct
7 Correct 27 ms 35656 KB Output is correct
8 Correct 127 ms 36588 KB Output is correct
9 Correct 126 ms 36552 KB Output is correct
10 Correct 92 ms 35860 KB Output is correct
11 Correct 140 ms 35680 KB Output is correct
12 Correct 21 ms 35668 KB Output is correct
13 Correct 25 ms 35716 KB Output is correct
14 Correct 22 ms 35680 KB Output is correct
15 Correct 23 ms 35688 KB Output is correct
16 Correct 22 ms 35680 KB Output is correct
17 Correct 63 ms 35816 KB Output is correct
18 Correct 64 ms 35880 KB Output is correct
19 Correct 108 ms 36568 KB Output is correct
20 Correct 167 ms 37968 KB Output is correct
21 Correct 137 ms 37392 KB Output is correct
22 Correct 117 ms 36940 KB Output is correct
23 Correct 136 ms 38088 KB Output is correct
24 Correct 104 ms 37324 KB Output is correct
25 Correct 86 ms 36948 KB Output is correct
26 Correct 86 ms 36944 KB Output is correct
27 Correct 22 ms 35668 KB Output is correct
28 Correct 21 ms 35744 KB Output is correct
29 Correct 22 ms 35636 KB Output is correct
30 Correct 22 ms 35684 KB Output is correct
31 Correct 22 ms 35744 KB Output is correct
32 Correct 27 ms 35772 KB Output is correct
33 Correct 26 ms 35700 KB Output is correct
34 Correct 28 ms 35740 KB Output is correct
35 Correct 24 ms 35744 KB Output is correct
36 Correct 60 ms 36532 KB Output is correct
37 Correct 95 ms 37204 KB Output is correct
38 Correct 120 ms 37832 KB Output is correct
39 Correct 126 ms 38088 KB Output is correct
40 Correct 110 ms 37572 KB Output is correct
41 Correct 76 ms 36808 KB Output is correct
42 Correct 74 ms 36824 KB Output is correct
43 Correct 112 ms 37316 KB Output is correct
44 Correct 21 ms 35680 KB Output is correct
45 Correct 22 ms 35644 KB Output is correct
46 Correct 22 ms 35656 KB Output is correct
47 Correct 23 ms 35652 KB Output is correct
48 Correct 25 ms 35740 KB Output is correct
49 Correct 38 ms 35680 KB Output is correct
50 Correct 39 ms 35700 KB Output is correct
51 Correct 41 ms 35700 KB Output is correct
52 Correct 39 ms 35760 KB Output is correct
53 Correct 84 ms 36536 KB Output is correct
54 Correct 147 ms 37960 KB Output is correct
55 Correct 156 ms 38212 KB Output is correct
56 Correct 122 ms 37588 KB Output is correct
57 Correct 229 ms 38984 KB Output is correct
58 Correct 139 ms 36780 KB Output is correct
59 Correct 161 ms 37464 KB Output is correct