Submission #932438

#	Time	Username	Problem	Language	Result	Execution time	Memory
932438		MisterReaper	Toll (BOI17_toll)	C++17	100 / 100	236 ms	100180 KiB

toll

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 5E4 + 5;
constexpr int L = 20;
constexpr int Inf = 1E9 + 5;

int ans[N][L][5][5];

void combine(int c[5][5], int a[5][5], int b[5][5]) {
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                c[i][j] = std::min(c[i][j], a[i][k] + b[k][j]);
            }
        }
    }
}

void solve() {
    std::fill_n(&ans[0][0][0][0], N * L * 5 * 5, Inf);

    int k, n, m, o;
    std::cin >> k >> n >> m >> o;

    for(int i = 1; i <= m; i++) {
        int a, b, t;
        std::cin >> a >> b >> t;
        ans[a / k][0][a % k][b % k] = t;
    }

    for(int lg = 1; lg < L; lg++) {
        for(int i = 0; i + (1 << lg) < (n + k - 1) / k; i++) {
            combine(ans[i][lg], ans[i][lg - 1], ans[i + (1 << (lg - 1))][lg - 1]);
        }
    }

    while(o--) {
        int a, b;
        std::cin >> a >> b;

        int res[5][5], cur = a / k;
        std::fill_n(&res[0][0], 5 * 5, Inf);
        for(int i = 0; i < 5; i++) res[i][i] = 0;
        for(int lg = L - 1; lg >= 0; lg--) {
            if(cur + (1 << lg) <= b / k) {
                int tmp[5][5];
                std::fill_n(&tmp[0][0], 5 * 5, Inf);
                combine(tmp, res, ans[cur][lg]);
                for(int i = 0; i < 5; i++) {
                    for(int j = 0; j < 5; j++) {
                        res[i][j] = tmp[i][j];
                    }
                }

                cur += (1 << lg);
            }
        }

        std::cout << (res[a % k][b % k] == Inf ? -1 : res[a % k][b % k]) << "\n";
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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