Submission #1176375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176375		minhpk	Toll (BOI17_toll)	C++20	0 / 100	164 ms	75576 KiB

toll

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll INF = 1e14;
 
vector<vector<ll>> multiply(const vector<vector<ll>> &A, const vector<vector<ll>> &B, int k) {
    vector<vector<ll>> C(k, vector<ll>(k, INF));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int s = 0; s < k; s++) {
                C[i][j] = min(C[i][j], A[i][s] + B[s][j]);
            }
        }
    }
    return C;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int k, a, m, q;
    cin >> k >> a >> m >> q;
    int blocks = (a + k - 1) / k;
    vector<vector<vector<ll>>> mat(blocks, vector<vector<ll>>(k, vector<ll>(k, INF)));
    for (int i = 0; i < blocks; i++){
        for (int j = 0; j < k; j++){
            mat[i][j][j] = 0;
        }
    }
 
    for (int i = 0; i < m; i++){
        ll x, y, t;
        cin >> x >> y >> t;
        ll bx = x / k, by = y / k;
        if (by == bx + 1) {
            mat[bx][x % k][y % k] = min(mat[bx][x % k][y % k], t);
        }
    }
 
    int L = floor(log2(blocks)) + 1;
    vector<vector<vector<vector<ll>>>> st(blocks, vector<vector<vector<ll>>>(L, vector<vector<ll>>(k, vector<ll>(k, INF))));
 
    for (int i = 0; i < blocks; i++){
        st[i][0] = mat[i];
    }
 
    for (int l = 1; l < L; l++){
        for (int i = 0; i + (1 << l) <= blocks; i++){
            st[i][l] = multiply(st[i][l-1], st[i + (1 << (l-1))][l-1], k);
        }
    }
 
    while(q--){
        ll x, y;
        cin >> x >> y;
        ll bx = x / k, by = y / k;
        if (bx == by) {
            cout << -1 << "\n";
            continue;
        }
 
        vector<vector<ll>> res(k, vector<ll>(k, INF));
        for (int i = 0; i < k; i++){
            res[i][i] = 0;
        }
 
        int idx = bx; 
        int remain = by - bx;
 
        for (int p = L - 1; p >= 0; p--){
            if ((1 << p) <= remain) {
                res = multiply(res, st[idx][p], k);
                idx += (1 << p);
                remain -= (1 << p);
            }
        }
 
        ll ans = res[x % k][y % k];
        if (ans >= INF) cout << -1 << "\n";
        else cout << ans << "\n";
    }
 
    return 0;
}

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