Submission #997999

#	Time	Username	Problem	Language	Result	Execution time	Memory
997999		Nailuj_217	Toll (BOI17_toll)	C++17	100 / 100	187 ms	41916 KiB

toll

#include <bits/stdc++.h>
#define l long long 
using namespace std;

struct LayerConnnection {
    l startlayer, endlayer;
    array<array<l, 5>, 5> min_weights;

};

l k, n, m, q;
const l LEN = 50005;
const l INF = 1LL<<60;

array<vector<pair<l, l>>, LEN> adj;
array<array<l, 20>, LEN> adj_matrix;
array<LayerConnnection, LEN*4+10> tree;


LayerConnnection build_tree(l i, l s, l f) {
    
    for (int a = 0; a < 5; a++) tree[i].min_weights[a].fill(INF);
    tree[i].startlayer = s;
    tree[i].endlayer = f;
    if (s == f) {
        for (int a = 0; a < k; a++) tree[i].min_weights[a][a] = 0;
        return tree[i];
    }

    LayerConnnection left = build_tree(i*2, s, (s+f)/2);
    LayerConnnection right = build_tree(i*2+1, (s+f)/2+1, f);

    for (int a = 0; a < k; a++) {
        for (int b = 0; b < k; b++) {
            for (int c = 0; c < k; c++) {
                if (!adj_matrix[((s+f)/2-1)*k+b][c]) continue;
                for (int d = 0; d < k; d++) {
                    tree[i].min_weights[a][d] = min(tree[i].min_weights[a][d], left.min_weights[a][b] + adj_matrix[((s+f)/2-1)*k+b][c] + right.min_weights[c][d]);
                }
            }
        }
    }

    return tree[i];

}


LayerConnnection query_tree(l i, l s, l f, l a, l b) {
    if (a > f || b < s) {
        LayerConnnection node = {-1, -1};
        return node;
    }
    if (a <= s && b >= f) return tree[i];

    LayerConnnection node = {s, f};
    for (int a = 0; a < k; a++) node.min_weights[a].fill(INF);
    LayerConnnection left = query_tree(i*2, s, (s+f)/2, a, b);
    LayerConnnection right = query_tree(i*2+1, (s+f)/2+1, f, a, b);

    if (left.startlayer == -1) return right;
    if (right.startlayer == -1) return left;


    for (int a = 0; a < k; a++) {
        for (int b = 0; b < k; b++) {
            for (int c = 0; c < k; c++) {
                if (!adj_matrix[((s+f)/2-1)*k+b][c]) continue;
                for (int d = 0; d < k; d++) {
                    node.min_weights[a][d] = min(node.min_weights[a][d], left.min_weights[a][b] + adj_matrix[((s+f)/2-1)*k+b][c] + right.min_weights[c][d]);
                }
            }
        }
    }

    return node;

}


int main() {

    cin >> k >> n >> m >> q;
    l a, b, w;

    for (int i = m; i--;) {
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj_matrix[a][b%k] = w;
    }

    build_tree(1, 1, n/k + 1);

    LayerConnnection node;

    while (q--) {
        cin >> a >> b;
        node = query_tree(1, 1, n/k+1, a/k+1, b/k+1);
        if (node.min_weights[a%k][b%k] < (1LL<<58)) cout << node.min_weights[a%k][b%k] << endl;
        else cout << -1 << endl;
    }


    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44