Submission #696923

#	Time	Username	Problem	Language	Result	Execution time	Memory
696923		vjudge1	Toll (BOI17_toll)	C++17	100 / 100	77 ms	36972 KiB

toll

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
using ll = long long;
int kk, n, m, q;
struct Matrix {
    ll a[5][5];
    inline ll *operator[](size_t x) {
        return a[x];
    }
    inline const ll *operator[](size_t x) const {
        return a[x];
    }
} INF;
Matrix merge(const Matrix &a, const Matrix &b) {
    Matrix c = INF;

    for (int i = 0; i < kk; i++)
        for (int j = 0; j < kk; j++)
            for (int k = 0; k < kk; k++)
                c[i][j] = min(c[i][j], a[i][k] + b[k][j]);

    return c;
}
Matrix a[N];
struct TNode {
    int l, r;
    Matrix v;
} t[N << 2];
inline int lc(int pos) {
    return pos << 1;
};
inline int rc(int pos) {
    return pos << 1 | 1;
}
void build(int pos, int l, int r) {
    t[pos].l = l;
    t[pos].r = r;

    if (l == r) {
        t[pos].v = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(lc(pos), l, mid);
    build(rc(pos), mid + 1, r);
    t[pos].v = merge(t[lc(pos)].v, t[rc(pos)].v);
}
Matrix query(int pos, int l, int r) {
    if (t[pos].l == l && t[pos].r == r)
        return t[pos].v;

    int mid = (t[pos].l + t[pos].r) >> 1;

    if (r <= mid)
        return query(lc(pos), l, r);
    else if (l > mid)
        return query(rc(pos), l, r);
    else
        return merge(query(lc(pos), l, mid), query(rc(pos), mid + 1, r));
}
int main() {
    ios::sync_with_stdio(false);
    cin >> kk >> n >> m >> q;

    for (int i = 0; i < kk; i++)
        for (int j = 0; j < kk; j++)
            INF[i][j] = LLONG_MAX >> 2;

    for (int i = 0; i <= n / kk; i++)
        a[i] = INF;

    for (int i = 1; i <= m; i++) {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        a[t2 / kk][t1 % kk][t2 % kk] = t3;
    }

    build(1, 0, n / kk);

    while (q--) {
        int t1, t2;
        cin >> t1 >> t2;

        if (t1 / kk >= t2 / kk) {
            cout << -1 << endl;
            continue;
        }

        ll ans = query(1, t1 / kk + 1, t2 / kk)[t1 % kk][t2 % kk];

        if (ans == LLONG_MAX >> 2)
            ans = -1;

        cout << ans << endl;
    }

    return 0;
}

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