oj.uz

Submission #590707

# Submission time Handle Problem Language Result Execution time Memory
590707 2022-07-06T09:03:59 Z minhi1 Toll (BOI17_toll) C++14
0 / 100
 21 ms 30316 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;
  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(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;
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 30284 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 30248 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 7 ms 14932 KB Output is correct
2 Correct 6 ms 14932 KB Output is correct
3 Correct 7 ms 14932 KB Output is correct
4 Correct 6 ms 14932 KB Output is correct
5 Correct 5 ms 14932 KB Output is correct
6 Correct 6 ms 14932 KB Output is correct
7 Correct 7 ms 15064 KB Output is correct
8 Correct 7 ms 15060 KB Output is correct
9 Correct 7 ms 15060 KB Output is correct
10 Runtime error 21 ms 30316 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14932 KB Output is correct
2 Correct 6 ms 14932 KB Output is correct
3 Correct 7 ms 14932 KB Output is correct
4 Correct 6 ms 14932 KB Output is correct
5 Correct 5 ms 14932 KB Output is correct
6 Correct 6 ms 14932 KB Output is correct
7 Correct 7 ms 15064 KB Output is correct
8 Correct 7 ms 15060 KB Output is correct
9 Correct 7 ms 15060 KB Output is correct
10 Runtime error 21 ms 30316 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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