oj.uz

Submission #676443

# Submission time Handle Problem Language Result Execution time Memory
676443 2022-12-30T22:57:39 Z bogdanvladmihai Toll (BOI17_toll) C++14
10 / 100
 240 ms 83720 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = (int)1e9;

int K, N, M, Q;

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

signed 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 197 ms 83720 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 216 ms 68292 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 26 ms 1364 KB Output is correct
8 Correct 27 ms 1272 KB Output is correct
9 Correct 191 ms 83648 KB Output is correct
10 Correct 240 ms 59708 KB Output is correct
11 Correct 222 ms 68212 KB Output is correct
12 Correct 192 ms 59628 KB Output is correct
13 Correct 185 ms 37380 KB Output is correct
14 Correct 132 ms 33876 KB Output is correct
15 Correct 124 ms 37368 KB Output is correct
16 Correct 164 ms 37364 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 2 ms 1376 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 2 ms 1376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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