Submission #1301338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301338		Born_To_Laugh	Toll (BOI17_toll)	C++17	100 / 100	196 ms	153828 KiB

toll

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;
const int maxn = 5e4 + 10;
int k, n, m, q;
vector<pair<int,int>> adj[maxn];
vector<vector<vector<vector<ll>>>> dp;
ll ope(int a, int b){
    vector<ll> dist(k + 1, INF);
    dist[a % k] = 0;
    int cur = a / k;
    int sth = b / k - a / k;
    if(sth <= 0)return -1;
    for(int j=0; j<20; ++j){
        if(sth & (1 << j)){
            vector<ll> nxt = dist;
            for(int x = 0; x < k; ++x){
                ll val = INF;
                for(int y = 0; y < k; ++y){
                    val = min(val, dist[y] + dp[cur][j][y][x]);
                }
                nxt[x] = val;
            }
            dist = nxt;
            cur += (1 << j);
        }
    }
    if(dist[b % k] < INF)return dist[b % k];
    else return -1;
}
void solve(){
    cin >> k >> n >> m >> q;
    dp.assign(
        (int)n / k + 1,
        vector<vector<vector<ll>>> (
            20,
            vector<vector<ll>> (
                k + 1,
                vector<ll> (
                    k + 1,
                    INF
                )
            )
        )
    );
    for(int i=1; i<=m; ++i){
        int a, b, c;cin >> a >> b >> c;
        adj[a].push_back({b, c});
        dp[a / k][0][a % k][b % k] = c;
        // cout << a / k << ' ' << 0 << ' ' << a % k << ' ' << b % k << ' ' << c << " ?? \n";
    }
    for(int i=(int)n / k; i>=0; --i){
        for(int j=1; j<20; ++j){
            if(i + (1 << j) > int(n / k))break;
            for(int x = 0; x < k; ++x){
                for(int y = 0; y < k; ++y){
                    for(int z = 0; z < k; ++z){
                        dp[i][j][x][y] = min(
                            dp[i][j][x][y],
                            dp[i][j - 1][x][z] + dp[i + (1 << (j - 1))][j - 1][z][y]
                        );
                    }
                    // cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << dp[i][j][x][y] << '\n';
                }
            }
        }
    }
    while(q--){
        int a, b;cin >> a >> b;
        cout << ope(a, b) << '\n';
    }
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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