oj.uz

Submission #676441

# Submission time Handle Problem Language Result Execution time Memory
676441 2022-12-30T22:56:46 Z bogdanvladmihai Toll (BOI17_toll) C++14
0 / 100
 245 ms 84572 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = (int)1e9;

int K, N, M, Q;

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

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

    dp.resize((N / K + 1) + 2, vector<vector<vector<int>>>(ceil(log2(N / K)) + 3, 
                            vector<vector<int>>(K, vector<int>(K, INF))));
    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 - 1)) <= (N + K - 1) / K; l++) {
        for (int g = 0; g + (1 << l) < (N + K - 1) / K; 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, INF));
        for (int j = 0; j < K; j++) {
            answer[j][j] = 0;
        }

        int len = b / K - a / K + 1, lst = a / K;
        for (int l = ceil(log2(len)) + 2; l >= 0; l--) {
            if ((len & (1 << l)) != 0) {
                vector<vector<int>> tmp(K, vector<int>(K, INF));
                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] == INF) {
            cout << "-1\n";
        } else {
            cout << answer[a % K][b % K] << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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