Submission #1007275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007275		overwatch9	Toll (BOI17_toll)	C++17	100 / 100	199 ms	23640 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int K, N, M, O;
vector <vector <pair <int, int>>> adj;
struct node {
    vector <vector <ll>> dis;
    node () {
        dis = vector <vector <ll>> (K, vector <ll> (K, 1e18));
    }
};
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <node> tree;
    stree (int s) {
        tree.resize(s * 4);
    }
    node combine(node a, node b, int l, int r) {
        node c;
        int tm = (l + r) / 2;
        for (int l1 = 0; l1 < K; l1++) {
            for (int l2 = 0; l2 < K; l2++) {
                for (int i = K*tm; i < K*(tm+1); i++) {
                    for (auto tp : adj[i]) {
                        int j = tp.first, w = tp.second;
                        c.dis[l1][l2] = min(c.dis[l1][l2], a.dis[l1][i % K] + w + b.dis[j % K][l2]);
                    }
                }
            }
        }
        return c;
    }
    void pushup(int v, int l, int r) {
        node a = tree[lc];
        node b = tree[rc];
        tree[v] = combine(a, b, l, r);
    }
    void build(int v, int tl, int tr) {
        if (tl == tr) {
            for (int i = 0; i < K; i++)
                tree[v].dis[i][i] = 0;
            return;
        }
        int tm = (tl + tr) / 2;
        build(lc, tl, tm);
        build(rc, tm+1, tr);
        pushup(v, tl, tr);
    }
    node query(int v, int tl, int tr, int l, int r) {
        if (tl >= l && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        if (r <= tm)
            return query(lc, tl, tm, l, r);
        if (l >= tm+1)
            return query(rc, tm+1, tr, l, r);
        node a = query(lc, tl, tm, l, r);
        node b = query(rc, tm+1, tr, l, r);
        return combine(a, b, tl, tr);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> K >> N >> M >> O;
    adj.resize(N+1);
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
    }
    stree tree((N-1)/K + 1);
    tree.build(1, 0, (N-1)/K);
    while (O--) {
        int a, b;
        cin >> a >> b;
        node res = tree.query(1, 0, (N-1)/K, a/K, b/K);
        ll ans = res.dis[a % K][b % K];
        if (ans == 1e18) 
            ans = -1;
        cout << ans << '\n';
    }
}

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