Submission #1005372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005372		tvladm2009	Toll (BOI17_toll)	C++17	100 / 100	99 ms	170064 KiB

toll

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;

const int N = 5e4 + 7;
const ll INF = 1e18;

int k, n, m, o;

struct Matrix {
    ll mat[5][5];
        
    Matrix() {
        for (int x = 0; x < 5; ++x) {
            for (int y = 0; y < 5; ++y) {
                mat[x][y] = INF;
            }
        }
    }

    Matrix operator * (Matrix other) {
        Matrix c;
        for (int x = 0; x < k; ++x) {
            for (int y = 0; y < k; ++y) {
                for (int z = 0; z < k; ++z) {
                    c.mat[x][y] = min(c.mat[x][y], mat[x][z] + other.mat[z][y]);
                }
            }
        }
        return c;
    }
};

Matrix dist[N][17];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> k >> n >> m >> o;
    while (m--) {
        int a, b, t;
        cin >> a >> b >> t;
        dist[a / k][0].mat[a % k][b % k] = t;
    }
    int layers = (n + k - 1) / k;
    for (int j = 1; j < 17; ++j) {
        for (int i = 0; i + (1 << j) < layers; ++i) {
            dist[i][j] = dist[i][j - 1] * dist[i + (1 << (j - 1))][j - 1];;
        }
    }

    while (o--) {
        int a, b;
        cin >> a >> b;
        Matrix ans;
        for (int i = 0; i < 5; ++i) {
            ans.mat[i][i] = 0;
        }
        int cur = a / k;
        for (int i = 16; i >= 0; --i) {
            if (cur + (1 << i) <= b / k) {
                ans = ans * dist[cur][i];
                cur += (1 << i);
            }
        }
        cout << (ans.mat[a % k][b % k] == INF ? -1 : ans.mat[a % k][b % k]) << "\n";
    }
    return 0;
}

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