Submission #1216127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216127		DangKhoizzzz	Toll (BOI17_toll)	C++20	100 / 100	101 ms	55256 KiB

toll

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 5e4 + 7;

int k, n, m, o, dp[maxn][7][20], cur[7], lst[7];

void solve()
{
    cin >> k >> n >> m >> o;

    for(int i = 0; i < maxn; i++)
    {
        for(int j = 0; j < 7; j++)
        {
            for(int z = 0; z < 20; z++) dp[i][j][z] = INF;
        }
    }

    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dp[u][v%k][0] = min(dp[u][v%k][0], w);
    }

    for(int j = 1; j < 20; j++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int x = 0; x < k; x++)
            {
                for(int y = 0; y < k; y++)
                {
                    int mid = ((1 << (j-1)) + i/k)*k + x;
                    int ed = ((1 << j) + i/k)*k + y;

                    if(ed >= n) break;
                    dp[i][y][j] = min(dp[i][y][j], dp[i][x][j-1] + dp[mid][y][j-1]);
                }
            }
        }
    }


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

        int step = b/k - a/k;

        fill(cur, cur+k, INF);
        fill(lst, lst+k, INF);


        int id = (a/k)*k;
        cur[a%k] = 0;

        for(int i = 0; i < 19; i++)
        {
            if((step >> i)&1)
            {
                for(int j = 0; j < k; j++)
                {
                    lst[j] = cur[j];
                    cur[j] = INF;
                }
                for(int x = 0; x < k; x++)
                {
                    for(int y = 0; y < k; y++)
                    {
                        cur[y] = min(lst[x] + dp[id+x][y][i], cur[y]);
                    }
                }
                id += (1 << i)*k;
            }
        }
        if(cur[b%k] == INF) cout << -1 << '\n';
        else cout << cur[b%k] << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("inp.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    solve();
    return 0;
}

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