# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
856761 | 2023-10-04T13:05:03 Z | vjudge1 | Toll (BOI17_toll) | C++14 | 44 ms | 78940 KB |
#include <bits/stdc++.h> using namespace std; #define task "" const int INF = 1e9 + 7; const int MAX = 50005; int k, n, m, q; int dp[16][MAX][5][5]; int tmp[5][5], newTmp[5][5]; bool minimize(int &x, const int &y) { if (x > y) { x = y; return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> k >> n >> m >> q; for (int j = 0; (1 << j) <= n; ++j) { for (int i = 0; i < n; ++i) { for (int a = 0; a < k; ++a) for (int b = 0; b < k; ++b) dp[j][i][a][b] = INF; } } while (m--) { int a, b, t; cin >> a >> b >> t; minimize(dp[0][a / k][a % k][b % k], t); } for (int j = 1; (1 << j) <= n; ++j) { for (int i = 0; i < n; ++i) if (i / k + (1 << j) <= (n - 1) / k) { int a = i / k, b = i % k; for (int c = 0; c < k; ++c) { for (int d = 0; d < k; ++d) minimize(dp[j][a][b][d], dp[j - 1][a][b][c] + dp[j - 1][a + (1 << j - 1)][c][d]); } } } while (q--) { int a, b; cin >> a >> b; int s = a / k, t = b / k; if (s == t) { cout << (a != b ? -1 : 0) << '\n'; continue; } memset(tmp, 0, sizeof tmp); for (int j = 0, l = t - s; (1 << j) <= l; ++j) { if (l >> j & 1) { for (int a = 0; a < k; ++a) { for (int b = 0; b < k; ++b) { newTmp[a][b] = INF; } } for (int a = 0; a < k; ++a) { for (int b = 0; b < k; ++b) { for (int c = 0; c < k; ++c) minimize(newTmp[a][c], tmp[a][b] + dp[j][s][b][c]); } } for (int a = 0; a < k; ++a) { for (int b = 0; b < k; ++b) tmp[a][b] = newTmp[a][b]; } s += 1 << j; } } cout << (tmp[a % k][b % k] == INF ? -1 : tmp[a % k][b % k]) << '\n'; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 78940 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6608 KB | Output is correct |
4 | Correct | 1 ms | 6492 KB | Output is correct |
5 | Correct | 3 ms | 21084 KB | Output is correct |
6 | Correct | 3 ms | 21084 KB | Output is correct |
7 | Correct | 3 ms | 21084 KB | Output is correct |
8 | Correct | 37 ms | 78680 KB | Output is correct |
9 | Correct | 37 ms | 78720 KB | Output is correct |
10 | Correct | 21 ms | 78680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 44 ms | 78932 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6488 KB | Output is correct |
2 | Incorrect | 1 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6488 KB | Output is correct |
2 | Incorrect | 1 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 78940 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6608 KB | Output is correct |
4 | Correct | 1 ms | 6492 KB | Output is correct |
5 | Correct | 3 ms | 21084 KB | Output is correct |
6 | Correct | 3 ms | 21084 KB | Output is correct |
7 | Correct | 3 ms | 21084 KB | Output is correct |
8 | Correct | 37 ms | 78680 KB | Output is correct |
9 | Correct | 37 ms | 78720 KB | Output is correct |
10 | Correct | 21 ms | 78680 KB | Output is correct |
11 | Incorrect | 44 ms | 78932 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |