Submission #672897

#	Time	Username	Problem	Language	Result	Execution time	Memory
672897		bogdanvladmihai	Toll (BOI17_toll)	C++14	10 / 100	249 ms	75048 KiB

toll

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

int K, N, M, Q;

vector<vector<vector<vector<int>>>> dp;

int main() {
    cin >> K >> N >> M >> Q;

    dp.resize((N / K + 1), vector<vector<vector<int>>>(ceil(log2(N / K)) + 1, 
                            vector<vector<int>>(K, vector<int>(K, INT_MAX / 2))));
    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 l = 1; (1 << l) <= (N + K - 1) / K; l++) {
        for (int g = 0; g < (N + K - 1) / K - (1 << l); g++) {
            for (int x = 0; x < K; x++) {
                for (int y = 0; y < K; y++) {
                    for (int z = 0; z < K; z++) {
                        dp[g][l][x][y] = min(dp[g][l][x][y], 
                                            dp[g][l - 1][x][z] + dp[g + (1 << (l - 1))][l - 1][z][y]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < Q; i++) {
        int a, b; cin >> a >> b;

        vector<vector<int>> answer(K, vector<int>(K, INT_MAX / 2));
        for (int j = 0; j < K; j++) {
            answer[j][j] = 0;
        }

        int len = b / K - a / K, lst = a / K;
        for (int l = ceil(log2(len)) + 1; l >= 0; l--) {
            if ((len & (1 << l)) != 0) {
                vector<vector<int>> tmp(K, vector<int>(K, INT_MAX / 2));
                for (int x = 0; x < K; x++) {
                    for (int y = 0; y < K; y++) {
                        for (int z = 0; z < K; z++) {
                            tmp[x][y] = min(tmp[x][y], answer[x][z] + dp[lst][l][z][y]);
                        }
                    }
                }

                answer = tmp;
                lst |= (1 << l);
            }
        }

        if (answer[a % K][b % K] >= INT_MAX / 2) {
            cout << "-1\n";
        } else {
            cout << answer[a % K][b % K] << "\n";
        }
    }

    return 0;
}

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