oj.uz

Submission #676442

# Submission time Handle Problem Language Result Execution time Memory
676442 2022-12-30T22:57:13 Z bogdanvladmihai Toll (BOI17_toll) C++14
10 / 100
 246 ms 84528 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, 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 200 ms 83704 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 218 ms 68324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 23 ms 1532 KB Output is correct
8 Correct 25 ms 1340 KB Output is correct
9 Correct 187 ms 84528 KB Output is correct
10 Correct 246 ms 61976 KB Output is correct
11 Correct 225 ms 69952 KB Output is correct
12 Correct 192 ms 60876 KB Output is correct
13 Correct 178 ms 32248 KB Output is correct
14 Correct 137 ms 35276 KB Output is correct
15 Correct 131 ms 31092 KB Output is correct
16 Correct 125 ms 30984 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 0 ms 212 KB Output is correct
6 Incorrect 3 ms 1364 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 0 ms 212 KB Output is correct
6 Incorrect 3 ms 1364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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