oj.uz

Submission #672738

# Submission time Handle Problem Language Result Execution time Memory
672738 2022-12-17T23:12:41 Z bogdanvladmihai Toll (BOI17_toll) C++14
0 / 100
 204 ms 76048 KB 
#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 / K))));
    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 - 1) / K; l++) {
        for (int g = 0; g <= (N - 1) / K - (1 << l) + 1; g++) {
            for (int m1 = 0; m1 < K; m1++) {
                for (int m2 = 0; m2 < K; m2++) {
                    for (int to = 0; to < K; to++) {
                        dp[g][l][m1][m2] = min(dp[g][l][m1][m2], 
                                            dp[g][l - 1][m1][to] + dp[g + (1 << (l - 1))][l - 1][to][m2]);
                    }
                }
            }
        }
    }

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

        vector<int> answer(K, INT_MAX / K);
        answer[a % K] = 0;

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

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

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

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 76048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 62372 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 76048 KB Output isn't correct
2 Halted 0 ms 0 KB -