Submission #1324253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324253		sh_qaxxorov_571	Toll (BOI17_toll)	C++20	46 / 100	3095 ms	20084 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e15;
int K, N, M, O;

// Qatlamlar orasidagi o'tish matritsasi
struct Matrix {
    long long mat[5][5];
    Matrix() {
        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j) mat[i][j] = INF;
    }
};

// Ikki matritsani birlashtirish (Floyd-Warshall kabi)
Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for(int i=0; i<K; ++i)
        for(int j=0; j<K; ++j)
            for(int k=0; k<K; ++k)
                C.mat[i][j] = min(C.mat[i][j], A.mat[i][k] + B.mat[k][j]);
    return C;
}

Matrix tree[50000]; // Segmentlar daraxti uchun (qatlamlar soni N/K)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> K >> N >> M >> O;
    
    // Qirralarni o'qish va qatlamlararo matritsalarni to'ldirish
    vector<Matrix> adj((N/K) + 1);
    for(int i=0; i<M; ++i) {
        int u, v, t;
        cin >> u >> v >> t;
        adj[u/K].mat[u%K][v%K] = t;
    }

    // Segmentlar daraxtini qurish yoki oddiy DP bilan hisoblash
    // (So'rovlar a dan b gacha bo'lgani uchun qatlamlar bo'ylab o'tamiz)
    
    while(O--) {
        int a, b;
        cin >> a >> b;
        if (a/K > b/K) {
            cout << -1 << endl;
            continue;
        }
        
        // Dinamik dasturlash: dp[i] - a dan joriy qatlamdagi i-tugungacha masofa
        vector<long long> dp(K, INF);
        dp[a%K] = 0;
        
        for (int g = a/K; g < b/K; ++g) {
            vector<long long> next_dp(K, INF);
            for (int i = 0; i < K; ++i) {
                if (dp[i] == INF) continue;
                for (int j = 0; j < K; ++j) {
                    next_dp[j] = min(next_dp[j], dp[i] + adj[g].mat[i][j]);
                }
            }
            dp = next_dp;
        }
        
        long long result = dp[b%K];
        if (result >= INF) cout << -1 << endl;
        else cout << result << endl;
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44