Submission #1251740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251740		akksss	Toll (BOI17_toll)	C++20	7 / 100	91 ms	56360 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 = 5;
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];
   map<pair<int,int>,int> wt;
   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;
       wt[{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]; 
                dp[i][k][j] = min(dp[i][k][j],val1 + val2);
            }         
         } 
      } 
   }
   vector<int> id;
   function<int(int,int)> query = [&](int a, int b){
       if(a == b) return 0ll;    
       if(a >= n) return 0ll;
       int val = 1e14;
       if(a/K >= b/K) return val;
       int ans = 1e14;
       int i = id.back();
       // dbg(i);
       id.pop_back();
       //dbg(i, id);
       for (int j = 0; j < K; j++) {
        //   dbg(dp[a][j][i], j);
           ans = min(ans, dp[a][j][i] + query( (a/K + (1<<i))*K + j, b));
           //dbg(ans);
       }
       return ans;
   };
  //  O = 1; 
   while(O--){
       int a, b; cin >> a >> b;
       //dbg(a, b);
       id.clear();
       if(a/K >= b/K){
           cout << "-1\n";
           continue;
       }
       if(a == b){
           cout << "0\n";
           continue;
       }
       int dist = b/K - a/K;
       for (int i=Log-1; i >= 0; i--){
          if(dist&(1<<i)) id.push_back(i); 
       }
       // dbg(dist, id);
       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: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44