Submission #1285745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285745		domi	Toll (BOI17_toll)	C++20	100 / 100	66 ms	69796 KiB

toll

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e4;
const int INF = 1e16;

using namespace std;

int k, n, m, q;

struct Node {
    int mat[7][7];

    static Node empty() {
        Node res;
        fill(&res.mat[0][0], &res.mat[0][0] + 7 * 7, INF);
        return res;
    }

    static Node id() {
        Node res;
        fill(&res.mat[0][0], &res.mat[0][0] + 7 * 7, INF);
        for (int i = 0; i < k; ++i) res.mat[i][i] = 0;
        return res;
    }

    static Node merge(const Node& left, const Node& right) {
        Node res = Node::empty();

        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j) {
                for (int d = 0; d < k; ++d)
                    res.mat[i][d] = min(res.mat[i][d], left.mat[i][j] + right.mat[j][d]);
            }
        }

        return res;
    }

};

Node f[NMAX + 5];

struct Seg {

    Node aint[4 * NMAX + 5];

    void build(int nod = 1, int st = 0, int dr = n / k - 1) {
        if (st == dr) {
            aint[nod] = f[st];
            return;
        }

        int m = (st + dr) >> 1;
        build(2 * nod, st, m);
        build(2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    Node query(int l, int r, int nod = 1, int st = 0, int dr = n / k - 1) {
        if (st > r || dr < l) return Node::id();
        if (l <= st && dr <= r) return aint[nod];

        int m = (st + dr) >> 1;
        return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
    }

}aint;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> k >> n >> m >> q;

    for (int i = 0; i < n / k; ++i)
        f[i] = Node::empty();

    for (int i = 0, a, b, t; i < m; ++i) {
        cin >> a >> b >> t;
        f[a / k].mat[a % k][b % k] = t;
    }

    aint.build();
    for (int i = 0, u, v; i < q; ++i) {
        cin >> u >> v;

        if ((u / k) >= (v / k)) {
            cout << "-1\n";
            continue;
        }

        auto ret = aint.query(u / k, v / k - 1);
        cout << (ret.mat[u % k][v % k] >= INF ? -1 : ret.mat[u % k][v % k]) << '\n';
    }
    return 0;
}

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