Submission #646651

#	Time	Username	Problem	Language	Result	Execution time	Memory
646651		mychecksedad	Toll (BOI17_toll)	C++17	100 / 100	147 ms	42756 KiB

toll

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 50000+10, F = 2147483646, K = 20;




int k, n, m, q;
ll dp[M][K][5];

void solve(){
    cin >> k >> n >> m >> q;
   
    for(int i = 0; i <= n + k; ++i){
        for(int j = 0; j < K; ++j){
            for(int l = 0; l < k; ++l)
                dp[i][j][l] = 1e18;
        }
    }


    for(int i = 0; i < m; ++i){
        int u, v, e; cin >> u >> v >> e;
        dp[u][0][v % k] = min(dp[u][0][v % k], 1ll * e);
    }
    for(int j = 1; j < K; ++j){
        for(int i = 0; i < n; ++i){
            for(int l = 0; l < k; ++l){
                for(int p = 0; p < k; ++p){
                    int d = (1<<(j-1)) * k;
                    if((i/k*k) + d + p < n){
                        dp[i][j][l] = min(dp[i][j][l], dp[i][j - 1][p] + dp[(i/k*k) + d + p][j - 1][l]); 
                    }
                }
            }
        }
    }
    for(;q--;){
        int a, b; cin >> a >> b;
        int dep = b/k - a/k;

        vector<ll> dist (k, ll(1e18));
        dist[a % k] = 0;

        int cur = a/k*k;

        for(int j = K - 1; j >= 0; --j){
            if((1<<j)&dep){
                vector<ll> t (k, ll(1e18));
                for(int l = 0; l < k; ++l){
                    for(int p = 0; p < k; ++p){
                        int d = (1<<j) * k;
                        t[l % k] = min(t[l % k], dist[p] + dp[cur + p][j][l]); 
                    }
                }
                cur += (1<<j)*k;

                dist = t;
            }
        }

        if(dist[b % k] == 1e18) cout << -1;
        else cout << dist[b % k];
        cout << '\n';
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void solve()':
toll.cpp:65:29: warning: unused variable 'd' [-Wunused-variable]
   65 |                         int d = (1<<j) * k;
      |                             ^
toll.cpp: In function 'int main()':
toll.cpp:87:16: warning: unused variable 'aa' [-Wunused-variable]
   87 |     int T = 1, aa;
      |                ^~

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