Submission #850950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
850950	2023-09-18T02:41:47 Z	NeroZein	Toll (BOI17_toll)	C++17	Compilation error	0 ms	0 KB

toll

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

#include "Deb.h"

const int Log = 17;
const long long INF = 1e15;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int k, n, m, q;
  cin >> k >> n >> m >> q;
  vector<vector<vector<long long>>> jump(Log, vector<vector<long long>> (n, vector<long long> (k, INF)));
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    jump[0][u][v % k] = w;
  }
  map<int, int> mp; 
  for (int i = 0; i < Log; ++i) {
    mp[1 << i] = i; 
  }
  for (int bit = 1; bit < Log; ++bit) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < k; ++j) {
        int x = i - (i % k) + (1 << (bit - 1)) * k + j; 
        if (x >= n) {
          break; 
        }
        for (int l = 0; l < k; ++l) {
          jump[bit][i][l] = min(jump[bit][i][l], jump[bit - 1][i][j] + jump[bit - 1][x][l]);
        }
      }
    }
  }
  while (q--) {
    int u, v;
    cin >> u >> v;
    int diff = v / k - u / k;
    if (diff <= 0) {
      cout << -1 << '\n';
      continue;
    }
    vector<pair<int, long long>> vec = {{u, 0}}; 
    while (diff) {
      int lsb = diff & -diff; 
      int ind = mp[lsb]; 
      diff -= lsb; 
      vector<pair<int, long long>> nvec;
      int org = vec.back().first;
      org -= org % k; 
      for (int i = 0; i < k; ++i) {
        int nnode = org + lsb * k + i;
        if (nnode >= n) {
          break; 
        }
        nvec.push_back({org + lsb * k + i, INF}); 
      }
      for (auto [x, y] : vec) {
        for (int j = 0; j < k; ++j) {
          nvec[j].second = min(nvec[j].second, y + jump[ind][x][j]);
        }
      }
      vec = nvec;
    }
    bool f = false;
    for (auto [i, j] : vec) {
      if (i == v && j < INF) {
        cout << j << '\n';
        f = true; 
        break;
      }
    }
    if (!f) {
      cout << -1 << '\n'; 
    }
  }
  return 0;
}

Compilation message

toll.cpp:4:10: fatal error: Deb.h: No such file or directory
    4 | #include "Deb.h"
      |          ^~~~~~~
compilation terminated.