Submission #1165193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165193		fryingduc	Toll (BOI17_toll)	C++20	100 / 100	138 ms	13380 KiB

toll

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e4 + 4;
const int B = 700;
int n, m, k, q;
int cost[maxn][5][5];
vector<int> dist[maxn / B + 5][B][5];

void minimize(int &x, int y) {
  if (x > y) x = y;
}

void solve() {
  cin >> k >> n >> m >> q;
  memset(cost, 0x3f, sizeof(cost));
  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    cost[v / k][v % k][u % k] = w;
  } 
  int nb = n / k;
  for (int i = 0; i <= nb / B + 2; ++i) {
    for (int j = 0; j < B; ++j) {
      for (int c = 0; c < k; ++c) {
        dist[i][j][c].resize(k, 1e9);
      }
    }
  }
  for (int bl = 0; bl <= nb / B; ++bl) {
    int en = min((bl + 1) * B - 1, nb);
    for (int c = 0; c < k; ++c) {
      dist[bl][en % B][c][c] = 0;
    }
    for (int j = en; j > bl * B; --j) {
      for (int c = 0; c < k; ++c) {
        for (int x = 0; x < k; ++x) {
          for (int y = 0; y < k; ++y) {
            minimize(dist[bl][(j - 1) % B][c][y], dist[bl][j % B][c][x] + cost[j][x][y]);
          }
        }
      }
    }
  }
  while (q--) {
    int s, t; cin >> s >> t;
    int bs = s / k, bt = t / k;
    if (bs >= bt) {
      cout << (s == t ? 0 : -1) << '\n';
      continue;
    }
    auto calc = [&](int s, int t) {
      vector<int> f(k, 1e9);
      f[t % k] = 0;
      for (int i = t / k; i > s / k; --i) {
        vector<int> nf(k, 1e9);
        for (int j = 0; j < k; ++j) {
          for (int c = 0; c < k; ++c) {
            nf[c] = min(nf[c], f[j] + cost[i][j][c]);
          }
        }
        f.swap(nf);
      }
      return f;
    };
    if (bs / B == bt / B) {
      vector<int> f = calc(s, t);
      cout << (f[s % k] == 1e9 ? -1 : f[s % k]) << '\n';
      continue;
    }
    vector<int> f(k, 1e9);
    for (int i = 0; i < k; ++i) {
      f[i] = dist[bs / B][bs % B][i][s % k];
    }
//    debug(f);
    for (int bl = bs / B + 1; bl < bt / B; ++bl) {
      vector<int> nf(k, 1e9);
      vector<vector<int>> d(k, vector<int>(k, 1e9));
      for (int j = 0; j < k; ++j) {
        d[j] = dist[bl][0][j];
      }
//      debug(bl, d);
      for (int c = 0; c < k; ++c) {
        for (int i = 0; i < k; ++i) {
          for (int j = 0; j < k; ++j) {
            if (max({d[c][i], f[j], cost[bl * B][i][j]}) < 1e9) {
              nf[c] = min(nf[c], d[c][i] + f[j] + cost[bl * B][i][j]);     
            }
          } 
        }
      }
      nf.swap(f);
    }
    int fb = bt / B * B;
    vector<int> d = calc(fb * k, t);
//    debug(d, f, fb * k);
    int mn = 1e9;
    for (int i = 0; i < k; ++i) {
      for (int j = 0; j < k; ++j) {
        if (max({cost[fb][i][j], d[i], f[j]}) < 1e9) {
          mn = min(mn, d[i] + f[j] + cost[fb][i][j]);     
        }
      } 
    }
    cout << (mn == 1e9 ? -1 : mn) << '\n';
  }
} 

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

  solve();

  return 0;
}
/*
3 14 5 5
0 5 9
5 8 10
0 3 7
7 9 8
4 7 10
0 12
0 5
0 7
7 12
0 3
*/

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