oj.uz

Submission #590704

# Submission time Handle Problem Language Result Execution time Memory
590704 2022-07-06T09:00:34 Z minhi1 Toll (BOI17_toll) C++14
0 / 100
 21 ms 30292 KB 
#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 = 14;
int k, n, m, o, dp[10025][LOG + 1][5][5], ans[5][5], tmp[5][5];
void sol() {
  cin >> k >> n >> m >> o;
  forn(i, 0, n/k) forn(j, 0, LOG) 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;
  }
  forn(j, 1, LOG) 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) rep(j, 0, k) {
      if (i == j) ans[i][j] = 0;
      else ans[i][j] = inf;
    }
    for(int i=LOG; i>=0; --i) if (cur + (1 << i) <= dest) {
      rep(i, 0, k) rep(j, 0, k) tmp[i][j] = inf;
      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] >= inf ? -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;
}

Compilation message

toll.cpp: In function 'void sol()':
toll.cpp:35:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 |       ckmin(dp[i][j][a][b], dp[i][j - 1][a][c] + dp[i + 1 << (j - 1)][j - 1][c][b]);
      |                                                     ~~^~~
toll.cpp:42:10: warning: unused variable 'first' [-Wunused-variable]
   42 |     bool first = true;
      |          ^~~~~
toll.cpp:27:78: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |   forn(i, 0, n/k) forn(j, 0, LOG) 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:27:49: note: in expansion of macro 'forn'
   27 |   forn(i, 0, n/k) forn(j, 0, LOG) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                 ^~~~
toll.cpp:27:78: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |   forn(i, 0, n/k) forn(j, 0, LOG) 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:27:35: note: in expansion of macro 'forn'
   27 |   forn(i, 0, n/k) forn(j, 0, LOG) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                   ^~~~
toll.cpp:27:76: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   27 |   forn(i, 0, n/k) forn(j, 0, LOG) forn(k, 0, 5) forn(l, 0, 5) dp[i][j][k][l] = inf;
      |                                                               ~~~~~~~~~~~~~^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 30292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 30212 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Runtime error 5 ms 3412 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Runtime error 5 ms 3412 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 30292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -