Submission #1096193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096193		anarch_y	Toll (BOI17_toll)	C++17	100 / 100	185 ms	89276 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    using Matrix = array<array<int, 5>, 5>;
    Matrix id;
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            if(i != j) id[i][j] = 1e9;
            else id[i][j] = 0;
        }
    }
    auto mult = [&](Matrix A, Matrix B){
        Matrix C;
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                C[i][j] = 1e9;
                for(int k=0; k<5; k++){
                    C[i][j] = min(C[i][j], A[i][k] + B[k][j]);
                }
            }
        }
        return C;
    };
    int k, n, m, q; 
    cin >> k >> n >> m >> q;
    n = (n-1)/k;
    Matrix to[n][18];
    for(int j=0; j<=17; j++){
        for(int i=0; i<n; i++){
            for(int x=0; x<5; x++){
                for(int y=0; y<5; y++) to[i][j][x][y] = 1e9;
            }
        }
    }
    while(m--){
        int a, b, t; cin >> a >> b >> t;
        int c = a/k, d = b/k;
        to[c][0][a-k*c][b-k*d] = t;
    }
    for(int j=1; j<=17; j++){
        for(int i=0; i+(1<<j)<=n; i++){
            to[i][j] = mult(to[i][j-1], to[i+(1<<(j-1))][j-1]);
        }
    }
    while(q--){
        int a, b; cin >> a >> b;
        int c = a/k, d = b/k;
        if(c >= d){
            cout << -1 << "\n";
            continue;
        }
        int y = d-c;
        Matrix C = id;
        for(int j=17; j>=0; j--){
            if(y & (1<<j)){
                C = mult(C, to[c][j]);
                c = c+(1<<j);
            }
        }
        c = a/k;
        int ans = C[a-k*c][b-k*d];
        if(ans == 1e9) 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