Submission #1125846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125846		b1hn_4n	Toll (BOI17_toll)	C++20	100 / 100	131 ms	88556 KiB

toll

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

template<class T>
inline bool minimize(T &a, const T &b) {return (a > b ? a = b, 1 : 0);}
template<class T>
inline bool maximize(T &a, const T &b) {return (a < b ? a = b, 1 : 0);}

const int N = 5e4 + 5;
const int LG = 18;

int n, m, k, q;
int f[N][LG][5][5], ans[5][5], tmp[5][5], inf;

void calc(int g[5][5], int a[5][5], int b[5][5]){
    for (int x = 0; x < k; ++x)
        for (int y = 0; y < k; ++y)
            for (int z = 0; z < k; ++z)
                minimize(g[x][y], a[x][z] + b[z][y]);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> k >> n >> m >> q;

    memset(f, 0x3f, sizeof f);
    inf = f[0][0][0][0];
    while (m--){
        int u, v, w;
        cin >> u >> v >> w;
        f[u / k][0][u % k][v % k] = w;
    }

    for (int j = 1; j < LG; ++j)
        for (int i = 0; i + (1 << j) < (n + k - 1) / k; ++i)
            calc(f[i][j], f[i][j-1], f[i + (1 << (j-1))][j-1]);

    while (q--){
        int u, v;
        cin >> u >> v;
        memset(ans, 0x3f, sizeof ans);
        for (int i = 0; i < k; ++i) ans[i][i] = 0;
        for (int x = u / k, y = v / k, i = 17; ~i; --i)
            if (x + (1 << i) <= y){
                memset(tmp, 0x3f, sizeof tmp);
                calc(tmp, ans, f[x][i]);
                memcpy(ans, tmp, sizeof ans);
                x += (1 << i);
            }
        cout << (ans[u % k][v % k] == inf ? -1 : ans[u % k][v % k]) << '\n';
    }
}

/*
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 1
*/

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