Submission #1040220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040220		turska	Toll (BOI17_toll)	C++17	100 / 100	44 ms	20316 KiB

toll

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


using ll = long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll M = 998244353;
// const ll M = 1e9 + 7;

#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second

const ll INFL = 1e18;
const int INF = 1e9;

int lift[17][50000][5];
void solve() {
    int K, N, M, O;
    cin >> K >> N >> M >> O;


    for (int i=0; i<17; i++) {
        for (int j=0; j<N; j++) {
            for (int k=0; k<K; k++) {
                lift[i][j][k] = 1e9;
            }
        }
    }

    for (int i=0; i<M; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        lift[0][a][b%K] = t;
    }

    for (int sz=1; sz<17; sz++) {
        for (int a=0; a<N; a++) {
            for (int to=0; to<K; to++) {
                for (int m=0; m<K; m++) {
                    int b = (a-(a%K))+(1<<(sz-1))*K+m;
                    if (b>=N) break;
                    lift[sz][a][to] = min(lift[sz][a][to], lift[sz-1][a][m]+lift[sz-1][b][to]);
                }
            }
        }
    }

    while (O--) {
        int a, b;
        cin >> a >> b;
        int d = ((b-(b%K))-(a-(a%K)))/K;
        if (d==0) {
            cout << "-1\n";
            continue;
        }
        int mn[5];
        int nxt[5];
        d--;
        for (int i=0; i<K; i++) mn[i] = lift[0][a][i];
        int cur = a-(a%K)+K;

        for (int i=0; i<17; i++) {
            if (!(d>>i&1)) continue;
            for (int j=0; j<K; j++) nxt[j] = 1e9;
            for (int j=0; j<K; j++) {
                for (int k=0; k<K; k++) {
                    nxt[k] = min(nxt[k], mn[j]+lift[i][cur+j][k]);
                }
            }
            cur += (1<<i)*K;
            d -= 1<<i;
            for (int j=0; j<K; j++) {
                mn[j] = nxt[j];
            }
        }
        assert(d==0);
        assert(cur==b-(b%K));

        int ans = mn[b%K];
        if (ans != 1e9) cout << ans << '\n';
        else cout << "-1\n";
    }
    



    
    
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);


    int tc = 1;
    // cin >> tc;
    while (tc--) solve();

}

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