Submission #590632

#	Time	Username	Problem	Language	Result	Execution time	Memory
590632		minhi1	Toll (BOI17_toll)	C++17	0 / 100	141 ms	169072 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/k) forn(j, 0, 16) forn(k, 0, 5) forn(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) {
          if (ans[a] >= inf) continue;
          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;
}

Compilation message (stderr)

toll.cpp: In function 'void sol()':
toll.cpp:34:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   34 |       ckmin(dp[i][j][a][b], dp[i][j - 1][a][c] + dp[i + 1 << (j - 1)][j - 1][c][b]);
      |                                                     ~~^~~
toll.cpp:26:77: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |   forn(i, 0, n/k) forn(j, 0, 16) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                              ~~~~~~~~~~~~~~~^~~~~
toll.cpp:2:43: note: within this loop
    2 | #define forn(i, a, b) for (int i = (a); i <= (int)(b); ++i)
      |                                           ^
toll.cpp:26:48: note: in expansion of macro 'forn'
   26 |   forn(i, 0, n/k) forn(j, 0, 16) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                ^~~~
toll.cpp:26:77: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |   forn(i, 0, n/k) forn(j, 0, 16) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                              ~~~~~~~~~~~~~~~^~~~~
toll.cpp:2:43: note: within this loop
    2 | #define forn(i, a, b) for (int i = (a); i <= (int)(b); ++i)
      |                                           ^
toll.cpp:26:34: note: in expansion of macro 'forn'
   26 |   forn(i, 0, n/k) forn(j, 0, 16) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                  ^~~~
toll.cpp:26:75: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   26 |   forn(i, 0, n/k) forn(j, 0, 16) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                              ~~~~~~~~~~~~~^

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