Submission #809185

#	Time	Username	Problem	Language	Result	Execution time	Memory
809185		serifefedartar	Toll (BOI17_toll)	C++17	100 / 100	257 ms	101496 KiB

toll

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 50005

int dp[MAXN][LOGN][5][5];
void merge(int q[5][5], int a[5][5], int b[5][5]) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                q[i][j] = min(q[i][j], a[i][k] + b[k][j]);
            }
        }
    }
}

int main() {
    fast
    int K, N, M, O;
    cin >> K >> N >> M >> O;

    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < LOGN; j++)
            for (int k = 0; k < 5; k++)
                for (int l = 0; l < 5; l++)
                    dp[i][j][k][l] = 1e9;

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dp[a/K][0][a%K][b%K] = c;
    }

    for (int i = 1; i < LOGN; i++) {
        for (int j = 0; j + (1<<i) - 1 < MAXN; j++) {
            merge(dp[j][i], dp[j][i-1], dp[j+(1<<(i-1))][i-1]);
        }
    }

    while (O--) {
        int a, b;
        cin >> a >> b;

        int h1 = a/K;
        int h2 = b/K;
        int n1 = a%K;
        int n2 = b%K;
        vector<int> ans(5, 1e9);
        ans[n1] = 0;
        for (int i = LOGN-1; i >= 0; i--) {
            if (h1 + (1<<i) <= h2) {
                vector<int> new_ans(5, 1e9);
                for (int old_rem = 0; old_rem < K; old_rem++) {
                    for (int rem = 0; rem < K; rem++) {
                        new_ans[rem] = min(new_ans[rem], ans[old_rem] + dp[h1][i][old_rem][rem]);
                    }
                }
                ans = new_ans;
                h1 += (1<<i);
            }
        }
        cout << (ans[n2] >= 1e9 ? -1 : ans[n2]) << "\n";
    }
}

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