oj.uz

Submission #672895

# Submission time Handle Problem Language Result Execution time Memory
672895 2022-12-18T21:13:16 Z bogdanvladmihai Toll (BOI17_toll) C++14
10 / 100
 226 ms 75932 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 - 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 / 2);
        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 / 2);
                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 / 2) {
            cout << "-1\n";
        } else {
            cout << answer[b % K] << "\n";
        }
    }
 
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 75020 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 213 ms 60844 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 20 ms 1336 KB Output is correct
8 Correct 27 ms 1304 KB Output is correct
9 Correct 206 ms 75932 KB Output is correct
10 Correct 226 ms 55452 KB Output is correct
11 Correct 212 ms 62548 KB Output is correct
12 Correct 175 ms 54412 KB Output is correct
13 Correct 182 ms 28588 KB Output is correct
14 Correct 138 ms 31468 KB Output is correct
15 Correct 122 ms 27320 KB Output is correct
16 Correct 113 ms 27384 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 Incorrect 1 ms 212 KB Output isn't correct
3 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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