Submission #1251875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251875		akksss	Toll (BOI17_toll)	C++20	46 / 100	3094 ms	70196 KiB

toll

#include "bits/stdc++.h"
using namespace std;

// For Ordered Set

/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// For snippet use pbds
*/
#define pi 3.141592653589793238
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define int long long

ll M = 1000000007;

// Solution Starts Here.....
const int NN = 5e4+5;
const int KK = 7;
const int Log = 25; 
int dp[NN][KK][Log];

void solve(){
   int K, n, m, O;
   cin >> K >> n >> m >> O;
   vector<int> adj[n];
   for (int i = 0; i < n; i++) {
       for (int j = 0; j < K; j++) {
          for (int k = 0; k < Log; k++) {
             dp[i][j][k] = 1e14; 
          } 
       }
   }
   for (int i = 0; i < m; i++) {
       int a, b, t; cin >> a >> b >> t;
       dp[a][b%K][0] = t; 
   }
    
   for (int j = 1; j < Log; j++) {
      for (int i = 0; i < n; i++) {
         for (int k = 0; k < K; k++) {
            int nxt = i/K + (1<<j) + k;
            if(nxt>=n) continue;
            // update dp[i][j][k]
            nxt = i/K + (1<<(j-1));
            for (int k1 = 0; k1 <K; k1++) {
                int val1 = dp[i][k1][j-1]; 
                int val2 = dp[K*nxt+k1][k][j-1]; 
                if(val1 < 1e14 and val2 < 1e14) dp[i][k][j] = min(dp[i][k][j],val1 + val2);
            }         
         } 
      } 
   }
   function<int(int,int)> query = [&](int a, int b){
       if(a == b) return 0ll;    
       int val = 1e14;
       if(a/K >= b/K) return val;

       int ans = 1e14;
       int i  = 0;
       int dist = b/K - a/K;
       for (; i < Log; i++) {
           if(dist & (1<<i)) break; 
       }
       for (int j = 0; j < K; j++) {
        //   dbg(dp[a][j][i], j);
           int Lval = query((a/K + (1<<i))*K + j, b);
           if(Lval < 1e14) ans = min(ans, dp[a][j][i] + Lval);
           //dbg(ans);
       }
       return ans;
   };
  //  O = 1; 
   while(O--){
       int a, b; cin >> a >> b;
       //dbg(a, b);
       int ans = query(a, b);
       if(ans >= 1e14){
            cout << "-1\n";
       }
       else cout << ans << "\n";
   } 
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    // cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        solve();
    }
}

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