Submission #590724

#	Time	Username	Problem	Language	Result	Execution time	Memory
590724		minhi1	Toll (BOI17_toll)	C++14	100 / 100	119 ms	83624 KiB

toll

#include <bits/stdc++.h>
#define forn(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define ll long long
#define pb push_back
using namespace std;
template<class X, class Y> bool ckmin(X &x, Y y) {
    if (x > y) {
        x = y; return true;
    }
    return false;
}
template<class X, class Y> bool ckmax(X &x, Y y) {
    if (x < y) {
        x = y; return true;
    }
    return false;
}
const int N = 5e4 + 25;
const ll linf = 1e16;
const int inf = (int)1e9 + 25;
/////////////////////////////////////////////////
int k, n, m, o, ans[5], tmp[5], dp[N][17][5][5];
void sol() {
  cin >> k >> n >> m >> o;
  forn(i, 0, n) forn(j, 0, 16) rep(k, 0, 5) rep(l, 0, 5) dp[i][j][k][l] = inf;
  forn(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    dp[u / k][0][u % k][v % k] = w;
  }
  rep(j, 1, 17) for(int i=0; i+(1<<j)<(n+k-1)/k; ++i) {
    rep(c, 0, k) rep(a, 0, k) rep(b, 0, k) {
      ckmin(dp[i][j][a][b], dp[i][j - 1][a][c] + dp[i + (1 << (j - 1))][j - 1][c][b]);
    }
  }
  while (o--) {
    int u, v;
    cin >> u >> v;
    int cur = u / k, dest = v / k;
    bool first = true;
    rep(i, 0, k) ans[i] = inf;
    for(int i=16; i>=0; --i) if (cur + (1 << i) <= dest) {
      if (first) {
        rep(b, 0, k) ans[b] = dp[cur][i][u % k][b];
        first = false;
      }
      else {
        rep(j, 0, k) tmp[j] = inf;
        rep(a, 0, k) rep(b, 0, k) ckmin(tmp[b], ans[a] + dp[cur][i][a][b]);
        rep(j, 0, k) ans[j] = tmp[j];
      }
      cur += (1 << i);
    }
    if (ans[v % k] >= inf) cout << -1 << '\n';
    else cout << ans[v % k] << '\n';
  }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifdef DHT
        freopen("hehe.inp", "r", stdin);
    #else
        //freopen("banhkhuc.inp", "r", stdin); freopen("banhkhuc.out", "w", stdout);
    #endif
    int t = 1;
//    cin >> t;
    forn(tt, 1, t) sol();
    return 0;
}

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