Submission #590715

#	Time	Username	Problem	Language	Result	Execution time	Memory
590715		minhi1	Toll (BOI17_toll)	C++14	100 / 100	123 ms	83604 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;
/////////////////////////////////////////////////
const int LOG = 16;
int k, n, m, o, dp[50000][LOG + 1][5][5], ans[5][5], tmp[5][5];
void sol() {
  cin >> k >> n >> m >> o;
  memset(dp, 0x3f, sizeof dp);
  forn(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    dp[u / k][0][u % k][v % k] = w;
  }
  forn(j, 1, LOG) for(int i=0; i+(1<<j)<(n+k-1)/k; ++i) {
    rep(a, 0, k) rep(b, 0, k) rep(c, 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;
    memset(ans, 0x3f, sizeof ans);
    rep(i, 0, k) ans[i][i] = 0;
    for(int i=LOG; i>=0; --i) if (cur + (1 << i) <= dest) {
      memset(tmp, 0x3f, sizeof tmp);
      rep(a, 0, k) rep(b, 0, k) rep(c, 0, k) {
        ckmin(tmp[a][b], ans[a][c] + dp[cur][i][c][b]);
      }
      memcpy(ans, tmp, sizeof ans);
      cur += (1 << i);
    }
    cout << (ans[u % k][v % k] == 0x3f3f3f3f ? -1 : ans[u % k][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