# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955858 | 2024-03-31T15:35:18 Z | Flan312 | Toll (BOI17_toll) | C++17 | 113 ms | 160344 KB |
#include <bits/stdc++.h> #define ll long long #define ld long double #define eb emplace_back #define task "" #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout); #define fi first #define se second #define pii pair <int, int> #define tii tuple <int, int, int> using namespace std; const int nmax = 5e4 + 2; int n, m, q, k; ll dp[nmax][16][5][5], ans[5], nxt[5]; /* dp[u][i][remU][remV]: đường đi ngắn nhất từ u*k + remU -> (u + 2^i - 1) * k + remv đường ngắn nhất từ đỉnh remU của tầng u đến đỉnh remV tầng u + 2^i - 1 */ void merge(int i, int j, int ii, int jj, int iii, int jjj) { for (int ru = 0; ru < k; ++ru) for (int rv = 0; rv < k; ++rv) for (int rt = 0; rt < k; ++rt) dp[i][j][ru][rv] = min(dp[i][j][ru][rv], dp[ii][jj][ru][rt] + dp[iii][jjj][rt][rv]); } int main() { if (ifstream(task".inp")) nx fast cin >> k >> n >> m >> q; memset(dp, 0x3f, sizeof dp); while(m--) { int a, b, t; cin >> a >> b >> t; dp[a / k][0][a % k][b % k] = t; } for (int j = 1; (1 << j) <= n / k; ++j) for (int i = 0; i + (1 << j) - 1 <= n / k; ++i) merge(i, j, i, j - 1, i + (1 << j - 1), j - 1); while(q--) { int a, b; cin >> a >> b; if (a == b) {cout << "0\n"; continue;} if (a / k >= b / k) {cout << "-1\n"; continue;} for (int i = 0; i < k; ++i) ans[i] = 1e18; ans[a % k] = 0; int layer = a / k, dist = b / k - a / k; for (int j = 0; (1 << j) <= dist; ++j) if (dist >> j & 1) { for (int r = 0; r < k; ++r) nxt[r] = 1e18; for (int x = 0; x < k; ++x) for (int y = 0; y < k; ++y) nxt[x] = min(nxt[x], ans[y] + dp[layer][j][y][x]); layer += (1 << j); for (int r = 0; r < k; ++r) swap(ans[r], nxt[r]); } cout << (ans[b % k] >= 1e18 ? -1 : ans[b % k]) << '\n'; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 158000 KB | Output is correct |
2 | Correct | 21 ms | 157020 KB | Output is correct |
3 | Correct | 20 ms | 156900 KB | Output is correct |
4 | Correct | 22 ms | 157272 KB | Output is correct |
5 | Correct | 21 ms | 157020 KB | Output is correct |
6 | Correct | 21 ms | 156804 KB | Output is correct |
7 | Correct | 21 ms | 157000 KB | Output is correct |
8 | Correct | 58 ms | 157940 KB | Output is correct |
9 | Correct | 62 ms | 157784 KB | Output is correct |
10 | Correct | 46 ms | 157016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 82 ms | 158544 KB | Output is correct |
2 | Correct | 25 ms | 156756 KB | Output is correct |
3 | Correct | 24 ms | 157020 KB | Output is correct |
4 | Correct | 23 ms | 156752 KB | Output is correct |
5 | Correct | 23 ms | 156924 KB | Output is correct |
6 | Correct | 23 ms | 156976 KB | Output is correct |
7 | Correct | 28 ms | 157008 KB | Output is correct |
8 | Correct | 26 ms | 157020 KB | Output is correct |
9 | Correct | 59 ms | 157884 KB | Output is correct |
10 | Correct | 72 ms | 159156 KB | Output is correct |
11 | Correct | 77 ms | 158776 KB | Output is correct |
12 | Correct | 62 ms | 158288 KB | Output is correct |
13 | Correct | 64 ms | 159288 KB | Output is correct |
14 | Correct | 49 ms | 158288 KB | Output is correct |
15 | Correct | 48 ms | 158144 KB | Output is correct |
16 | Correct | 47 ms | 158060 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 156756 KB | Output is correct |
2 | Correct | 20 ms | 157016 KB | Output is correct |
3 | Correct | 22 ms | 157016 KB | Output is correct |
4 | Correct | 21 ms | 156864 KB | Output is correct |
5 | Correct | 21 ms | 156756 KB | Output is correct |
6 | Correct | 23 ms | 157020 KB | Output is correct |
7 | Correct | 22 ms | 157036 KB | Output is correct |
8 | Correct | 22 ms | 156920 KB | Output is correct |
9 | Correct | 25 ms | 157012 KB | Output is correct |
10 | Correct | 54 ms | 157804 KB | Output is correct |
11 | Correct | 78 ms | 158532 KB | Output is correct |
12 | Correct | 76 ms | 159172 KB | Output is correct |
13 | Correct | 75 ms | 159356 KB | Output is correct |
14 | Correct | 71 ms | 158804 KB | Output is correct |
15 | Correct | 50 ms | 158028 KB | Output is correct |
16 | Correct | 52 ms | 158184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 156756 KB | Output is correct |
2 | Correct | 20 ms | 157016 KB | Output is correct |
3 | Correct | 22 ms | 157016 KB | Output is correct |
4 | Correct | 21 ms | 156864 KB | Output is correct |
5 | Correct | 21 ms | 156756 KB | Output is correct |
6 | Correct | 23 ms | 157020 KB | Output is correct |
7 | Correct | 22 ms | 157036 KB | Output is correct |
8 | Correct | 22 ms | 156920 KB | Output is correct |
9 | Correct | 25 ms | 157012 KB | Output is correct |
10 | Correct | 54 ms | 157804 KB | Output is correct |
11 | Correct | 78 ms | 158532 KB | Output is correct |
12 | Correct | 76 ms | 159172 KB | Output is correct |
13 | Correct | 75 ms | 159356 KB | Output is correct |
14 | Correct | 71 ms | 158804 KB | Output is correct |
15 | Correct | 50 ms | 158028 KB | Output is correct |
16 | Correct | 52 ms | 158184 KB | Output is correct |
17 | Correct | 74 ms | 158524 KB | Output is correct |
18 | Correct | 21 ms | 156760 KB | Output is correct |
19 | Correct | 21 ms | 156756 KB | Output is correct |
20 | Correct | 20 ms | 157004 KB | Output is correct |
21 | Correct | 22 ms | 156752 KB | Output is correct |
22 | Correct | 19 ms | 156752 KB | Output is correct |
23 | Correct | 22 ms | 156984 KB | Output is correct |
24 | Correct | 22 ms | 157020 KB | Output is correct |
25 | Correct | 22 ms | 157020 KB | Output is correct |
26 | Correct | 21 ms | 157012 KB | Output is correct |
27 | Correct | 55 ms | 157836 KB | Output is correct |
28 | Correct | 73 ms | 159056 KB | Output is correct |
29 | Correct | 78 ms | 159448 KB | Output is correct |
30 | Correct | 69 ms | 158804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 158000 KB | Output is correct |
2 | Correct | 21 ms | 157020 KB | Output is correct |
3 | Correct | 20 ms | 156900 KB | Output is correct |
4 | Correct | 22 ms | 157272 KB | Output is correct |
5 | Correct | 21 ms | 157020 KB | Output is correct |
6 | Correct | 21 ms | 156804 KB | Output is correct |
7 | Correct | 21 ms | 157000 KB | Output is correct |
8 | Correct | 58 ms | 157940 KB | Output is correct |
9 | Correct | 62 ms | 157784 KB | Output is correct |
10 | Correct | 46 ms | 157016 KB | Output is correct |
11 | Correct | 82 ms | 158544 KB | Output is correct |
12 | Correct | 25 ms | 156756 KB | Output is correct |
13 | Correct | 24 ms | 157020 KB | Output is correct |
14 | Correct | 23 ms | 156752 KB | Output is correct |
15 | Correct | 23 ms | 156924 KB | Output is correct |
16 | Correct | 23 ms | 156976 KB | Output is correct |
17 | Correct | 28 ms | 157008 KB | Output is correct |
18 | Correct | 26 ms | 157020 KB | Output is correct |
19 | Correct | 59 ms | 157884 KB | Output is correct |
20 | Correct | 72 ms | 159156 KB | Output is correct |
21 | Correct | 77 ms | 158776 KB | Output is correct |
22 | Correct | 62 ms | 158288 KB | Output is correct |
23 | Correct | 64 ms | 159288 KB | Output is correct |
24 | Correct | 49 ms | 158288 KB | Output is correct |
25 | Correct | 48 ms | 158144 KB | Output is correct |
26 | Correct | 47 ms | 158060 KB | Output is correct |
27 | Correct | 21 ms | 156756 KB | Output is correct |
28 | Correct | 20 ms | 157016 KB | Output is correct |
29 | Correct | 22 ms | 157016 KB | Output is correct |
30 | Correct | 21 ms | 156864 KB | Output is correct |
31 | Correct | 21 ms | 156756 KB | Output is correct |
32 | Correct | 23 ms | 157020 KB | Output is correct |
33 | Correct | 22 ms | 157036 KB | Output is correct |
34 | Correct | 22 ms | 156920 KB | Output is correct |
35 | Correct | 25 ms | 157012 KB | Output is correct |
36 | Correct | 54 ms | 157804 KB | Output is correct |
37 | Correct | 78 ms | 158532 KB | Output is correct |
38 | Correct | 76 ms | 159172 KB | Output is correct |
39 | Correct | 75 ms | 159356 KB | Output is correct |
40 | Correct | 71 ms | 158804 KB | Output is correct |
41 | Correct | 50 ms | 158028 KB | Output is correct |
42 | Correct | 52 ms | 158184 KB | Output is correct |
43 | Correct | 74 ms | 158524 KB | Output is correct |
44 | Correct | 21 ms | 156760 KB | Output is correct |
45 | Correct | 21 ms | 156756 KB | Output is correct |
46 | Correct | 20 ms | 157004 KB | Output is correct |
47 | Correct | 22 ms | 156752 KB | Output is correct |
48 | Correct | 19 ms | 156752 KB | Output is correct |
49 | Correct | 22 ms | 156984 KB | Output is correct |
50 | Correct | 22 ms | 157020 KB | Output is correct |
51 | Correct | 22 ms | 157020 KB | Output is correct |
52 | Correct | 21 ms | 157012 KB | Output is correct |
53 | Correct | 55 ms | 157836 KB | Output is correct |
54 | Correct | 73 ms | 159056 KB | Output is correct |
55 | Correct | 78 ms | 159448 KB | Output is correct |
56 | Correct | 69 ms | 158804 KB | Output is correct |
57 | Correct | 87 ms | 160344 KB | Output is correct |
58 | Correct | 64 ms | 157776 KB | Output is correct |
59 | Correct | 79 ms | 158784 KB | Output is correct |