Submission #1180881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180881		nguyenkhangninh99	Toll (BOI17_toll)	C++17	100 / 100	370 ms	167036 KiB

toll

#include <bits/stdc++.h>
 using namespace std;
 
#define int long long

const int maxn = 5e4 + 5;

array<array<int, 5>, 5> st[maxn][17];

array<array<int, 5>, 5> merge(array<array<int, 5>, 5> a, array<array<int, 5>, 5> b){
    array<array<int, 5>, 5> res;

    for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) res[i][j] = 1e15;

    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++) res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
        }
    }

    return res;
}
void solve(){
    for(int i = 0; i < maxn; i++){
        for(int j = 0; j < 17; j++){
            for(int k = 0; k < 5; k++){
                for(int l = 0; l < 5; l++) st[i][j][k][l] = 1e15;
            }
        }
    }

    int k, n, m, o; cin >> k >> n >> m >> o;
    for(int i = 1; i <= m; i++){
        int a, b, t; cin >> a >> b >> t;
        st[a / k][0][a % k][b % k] = t;
    }

    for(int j = 1; j <= 16; j++){
        for(int i = 0; i + (1 << (j - 1)) <= n / k; i++){
            st[i][j] = merge(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    while(o--){
        int a, b; cin >> a >> b;
        int x = a / k, y = b / k;
        
        array<array<int, 5>, 5> res;

        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                res[i][j] = 1e15;
            }
            res[i][i] = 0;
        }
        
        for(int j = 16; j >= 0; j--){
            if(x + (1 << j) <= y){
                res = merge(res, st[x][j]);
                x += (1 << j);
            }
        }

        cout << (res[a % k][b % k] == 1e15 ? -1 : res[a % k][b % k]) << "\n";
    }



}
signed main(){
	ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    solve();
}

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