# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
354298 | 2021-01-21T16:52:47 Z | parsabahrami | Toll (BOI17_toll) | C++11 | 123 ms | 47596 KB |
// Call my Name and Save me from The Dark #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 5e4 + 10, MOD = 1e9 + 7; int M[N], dp[22][5][N], n, k, q, m; vector<pii> in[N], out[N]; void divide(int l = 0, int r = (n - 1) / k + 1, int h = 0) { if (r - l < 3) return; int mid = (l + r) >> 1; //printf("l %d mid %d r %d\n", l, mid, r); for (int i = mid * k; i < mid * k + k; i++) dp[h][i % k][i] = 0; for (int i = mid * k - 1; i >= l * k; i--) { for (int j = 0; j < 5; j++) for (pii u : out[i]) { dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S); } } for (int i = mid * k + k; i < min(n, r * k); i++) { for (int j = 0; j < 5; j++) for (pii u : in[i]) { dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S); } } for (int i = mid; i < r; i++) M[i] ^= 1 << h; //for (int i = l * k; i < min(n, r * k); i++) for (int j = 0; j < 5; j++) printf("i %d j %d dp %d\n", i, j, dp[h][j][i]); divide(l, mid), divide(mid, r); } int main() { for (int i = 0; i < 18; i++) for (int j = 0; j < 5; j++) fill(dp[i][j], dp[i][j] + N, MOD); scanf("%d%d%d%d", &k, &n, &m, &q); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); out[u].push_back({v, w}); in[v].push_back({u, w}); } divide(); for (; q; q--) { int a, b; scanf("%d%d", &a, &b); if (a == b) printf("%d\n", 0); else if (a / k == b / k) printf("-1\n"); else if (b / k - a / k == 1) { int ret = -1; for (pii u : out[a]) if (u.F == b) ret = u.S; printf("%d\n", ret); } else { int h = __builtin_ctz(M[a / k] ^ M[b / k]); int ret = MOD; for (int i = 0; i < 5; i++) { ret = min(ret, dp[h][i][a] + dp[h][i][b]); } printf("%d\n", ret == MOD ? -1 : ret); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 101 ms | 47596 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 123 ms | 47468 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 40940 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 40940 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 101 ms | 47596 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |