# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
354295 |
2021-01-21T16:51:30 Z |
parsabahrami |
Toll (BOI17_toll) |
C++11 |
|
0 ms |
256 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[18][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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |