Submission #654685

#	Time	Username	Problem	Language	Result	Execution time	Memory
654685		HaYoungJoon	Toll (BOI17_toll)	C++14	100 / 100	124 ms	167560 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define INF 1e18

using namespace std;

ll dp[50001][17][5][5],K,n,m,Q, ans[5][5], tmp[5][5];

void combine(ll target[5][5], ll a[5][5], ll b[5][5]) {
    for (int i = 0; i < K; i++)
    for (int j = 0; j < K; j++) {
        target[i][j] = INF;
        for (int mid = 0; mid < K; mid++)
            target[i][j] = min(target[i][j],a[i][mid] + b[mid][j]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> K >> n >> m >> Q;
    int maxU = n/K + (n % K != 0);
    for (int i = 0; i <= maxU; i++)
        for (int j = 0; j <= 16; j++)
            for (int k = 0; k < K; k++)
                for (int l = 0; l < K; l++) dp[i][j][k][l] = INF;
    for (int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        dp[u/K][0][u%K][v%K] = w;
    }
    for (int i = maxU; i >= 0; i--) {
        for (int j = 1; i + (1 << j) - 1 <= maxU; j++) {
            combine(dp[i][j],dp[i][j-1],dp[i + (1 << (j-1))][j-1]);
        }
    }
    while (Q--) {
        int u,v;
        cin >> u >> v;
        int U = u/K, V = v/K;
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                if (i != j) ans[i][j] = INF;
                else ans[i][j] = 0;
        for (int i = 16; i >= 0; i--) {
            if (U + (1 << i) <= V) {
                for (int i = 0; i < K; i++)
                    for (int j = 0; j < K; j++) tmp[i][j] = ans[i][j];
                combine(ans,tmp,dp[U][i]);
                U += (1 << i);
            }
        }
        if (ans[u % K][v % K] == INF) cout << "-1\n";
        else cout << ans[u % K][v % K] << '\n';
    }
    return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/

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