Submission #1216108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216108		DangKhoizzzz	Toll (BOI17_toll)	C++20	0 / 100	64 ms	55164 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];

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 i = 0; i < n; i++)
    {
        for(int x = 0; x < k; x++)
        {
            for(int y = 0; y < k; y++)
            {
                for(int j = 1; j < 20; j++)
                {
                    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 , cur[k] , lst[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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44