Submission #1165164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165164		fryingduc	Toll (BOI17_toll)	C++20	0 / 100	286 ms	589824 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 = 3;
const int N = 1e4 + 4;
int n, m, k, q;
int eu[maxn], ev[maxn], ew[maxn];
vector<pair<int, int>> to[maxn];
int qs[maxn], qt[maxn];
int f[N][N];
int id[maxn];
int cost[maxn][5][5];
vector<int> dist[N / B][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) {
    cin >> eu[i] >> ev[i] >> ew[i];
    cost[ev[i] / k][ev[i] % k][eu[i] % k] = ew[i];
  } 
  int nb = n / k;
  for (int i = 0; i <= nb / B; ++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;
    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);
//      debug(f);
      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];
    }
    for (int bl = bs / B + 1; bl < bt / B; ++bl) {
      vector<int> nf(k, 1e9);
      vector<int> d(k, 1e9);
      for (int j = 0; j < k; ++j) {
        d[j] = dist[bl][0][j][s % k];
      }
      debug(bl, d);
      for (int c = 0; c < k; ++c) {
        for (int i = 0; i < k; ++i) {
          for (int j = 0; j < k; ++j) {
            nf[c] = min(nf[c], d[i] + f[j] + cost[bl * B][i][j]);     
          } 
        }
      }
      nf.swap(f);
    }
//    debug(f);
    vector<int> d = calc(bt / B * B, t);
    vector<int> nf(k, 1e9);
    for (int c = 0; c < k; ++c) {
      for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
          if (max({cost[bt * B][i][j], d[i], f[j]}) < 1e9) {
            nf[c] = min(nf[c], d[i] + f[j] + cost[bt * B][i][j]);     
          }
        } 
      }
    }
    int mn = *min_element(nf.begin(), nf.end());
    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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44