oj.uz

Submission #672897

# Submission time Handle Problem Language Result Execution time Memory
672897 2022-12-18T21:14:54 Z bogdanvladmihai Toll (BOI17_toll) C++14
10 / 100
 249 ms 75048 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 / 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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 60748 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 25 ms 1288 KB Output is correct
8 Correct 26 ms 1132 KB Output is correct
9 Correct 181 ms 74976 KB Output is correct
10 Correct 249 ms 53148 KB Output is correct
11 Correct 215 ms 60852 KB Output is correct
12 Correct 192 ms 53204 KB Output is correct
13 Correct 183 ms 26168 KB Output is correct
14 Correct 146 ms 29908 KB Output is correct
15 Correct 129 ms 26196 KB Output is correct
16 Correct 132 ms 26200 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 2 ms 1236 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 2 ms 1236 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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