Submission #985983

#	Time	Username	Problem	Language	Result	Execution time	Memory
985983		tfgs	Toll (BOI17_toll)	C++17	100 / 100	72 ms	82004 KiB

toll

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }

const int max_k = 5, max_n = 5e4;
int k, n, m, q, jump[16][max_n][max_k][max_k];

void solve() {
    cin >> k >> n >> m >> q; 

    for (int stp = 0; stp < 16; stp++) {
        for (int i = 0; i < n; i++) {
            for (int x = 0; x < k; x++) {
                for (int y = 0; y < k; y++) {
                    jump[stp][i][x][y] = inf;
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        jump[0][u/k][u%k][v%k] = w;
    }

    for (int stp = 1; stp < 16; stp++) {
        for (int i = 0; i < (n-1)/k; i++) if (i + (1 << (stp-1)) <= (n-1)/k){
            for (int z = 0; z < k; z++) {
                for (int x = 0; x < k; x++) {
                    for (int y = 0; y < k; y++) {
                        jump[stp][i][x][y] = min(jump[stp][i][x][y], jump[stp-1][i][x][z]+jump[stp-1][i+(1 << (stp-1))][z][y]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < q; i++) {
        vi dist(k, inf);
        int u, v; cin >> u >> v;
        int gap = v/k - u/k;
        int pos = u/k;
        int x = u%k;
        dist[x] = 0;
        for (int stp = 15; stp >= 0; stp--) if (gap & (1 << stp)) {
            auto DIST = dist;
            dist.assign(k, inf);
            for (int z = 0; z < k; z++) {
                for (int y = 0; y < k; y++) {
                    dist[y] = min(dist[y], DIST[z]+jump[stp][pos][z][y]);
                }
            }
            pos += 1 << stp;
        }

        int ans = dist[v%k];
        if (ans == inf) ans = -1;
        cout << ans << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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