Submission #1194988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194988		Hamed_Ghaffari	Toll (BOI17_toll)	C++20	100 / 100	73 ms	75080 KiB

toll

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

using pii = pair<int, int>;

#define X first
#define Y second
#define mins(a,b) (a = min(a,b))

const int MXN = 5e4+2, LOG = 16, MXK = 5, inf=1e9;

int k, n, m, q, rmq[LOG][MXN][MXK][MXK], ans[MXK][MXK], tmp[MXK][MXK];
vector<pii> g[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int m, q;
    cin >> k >> n >> m >> q;
    for(int i=0,u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    for(int i=0; i+1<=(n-1)/k; i++) {
        for(int u=0; u<k; u++)
            fill(rmq[0][i][u], rmq[0][i][u]+k, inf);
        for(int u=i*k; u<(i+1)*k; u++)
            for(auto [v, w] : g[u])
                mins(rmq[0][i][u%k][v%k], w);
    }
    for(int i=1; i<LOG; i++)
        for(int j=0; j+(1<<i)<=(n-1)/k; j++) {
            for(int u=0; u<k; u++)
                fill(rmq[i][j][u], rmq[i][j][u]+k, inf);
            for(int u=0; u<k; u++)
                for(int v=0; v<k; v++)
                    for(int w=0; w<k; w++)
                        mins(rmq[i][j][u][w], rmq[i-1][j][u][v] + rmq[i-1][j+(1<<(i-1))][v][w]);
        }
    for(int u=0; u<k; u++)
        fill(tmp[u], tmp[u]+k, inf);
    while(q--) {
        int a, b;
        cin >> a >> b;
        int l = a/k, d = b/k-a/k;
        if(d==0) {
            cout << "-1\n";
            continue;
        }
        bool fir=1;
        while(d) {
            int i = __lg(d&-d);
            if(fir) {
                for(int u=0; u<k; u++)
                    for(int v=0; v<k; v++)
                        ans[u][v] = rmq[i][l][u][v];
                fir = 0;
            }
            else {
                for(int u=0; u<k; u++)
                    for(int v=0; v<k; v++)
                        for(int w=0; w<k; w++)
                            mins(tmp[u][w], ans[u][v] + rmq[i][l][v][w]);
                for(int u=0; u<k; u++)
                    for(int v=0; v<k; v++)
                        ans[u][v] = tmp[u][v],
                        tmp[u][v] = inf;
            }
            l += 1<<i;
            d ^= 1<<i;
        }
        int res = ans[a%k][b%k];
        cout << (res==inf ? -1 : res) << '\n';
    }
    return 0;
}

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