Submission #677087

#	Time	Username	Problem	Language	Result	Execution time	Memory
677087		Cyanmond	Toll (BOI17_toll)	C++17	100 / 100	233 ms	21308 KiB

toll

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1ll << 40;

int K;

struct node {
    std::vector<std::vector<i64>> cost;

    node() : cost(K, std::vector(K, inf)) {
        for (int i = 0; i < K; ++i) {
            cost[i][i] = 0;
        }
    }

    void fill_inf() {
        std::fill(cost.begin(), cost.end(), std::vector(K, inf));
    }
};

node operate(const node &a, const node &b) {
    const int w = K;
    node res;
    res.fill_inf();

    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < w; ++j) {
            for (int k = 0; k < w; ++k) {
                res.cost[i][k] = std::min(res.cost[i][k], a.cost[i][j] + b.cost[j][k]);
            }
        }
    }

    return res;
    // O(K^3)
}

struct segment_tree {
    int n, size;
    std::vector<node> tree;

    void update(const int i) {
        tree[i] = operate(tree[2 * i], tree[2 * i + 1]);
    }

    segment_tree(const std::vector<node> &data) : n((int)data.size()) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        tree.resize(2 * size);
        for (int i = 0; i < n; ++i) {
            tree[i + size] = data[i];
        }
        for (int i = size - 1; i >= 1; --i) {
            update(i);
        }
    }

    node fold(int l, int r) {
        node pl, pr;
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1) {
                pl = operate(pl, tree[l++]);
            }
            if (r & 1) {
                pr = operate(tree[--r], pr);
            }
        }
        return operate(pl, pr);
    }
};

int main() {
    int N, M, O;
    std::cin >> K >> N >> M >> O;

    std::vector<int> A(M), B(M);
    std::vector<i64> T(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i] >> T[i];
    }

    std::vector<int> X(O), Y(O);
    for (int i = 0; i < O; ++i) {
        std::cin >> X[i] >> Y[i];
    }

    const int W = (N + K - 1) / K;
    std::vector<node> cost_table(W - 1);
    for (auto &e : cost_table) {
        e.fill_inf();
    }
    for (int i = 0; i < M; ++i) {
        const int p = A[i] / K;
        cost_table[p].cost[A[i] % K][B[i] % K] = T[i];
    }
    
    segment_tree seg(cost_table);
    for (int i = 0; i < O; ++i) {
        const int l = X[i] / K, r = Y[i] / K;
        const auto res = seg.fold(l, r);
        i64 ans = res.cost[X[i] % K][Y[i] % K];
        if (ans >= inf) {
            ans = -1;
        }
        std::cout << ans << std::endl;
    }
}

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