# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
985345 |
2024-05-17T16:20:05 Z |
OAleksa |
Toll (BOI17_toll) |
C++14 |
|
67 ms |
8276 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 69;
int n, m, k, q, dis[N][6], d[N];
vector<pair<int, int>> g[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> k >> n >> m >> q;
const int B = 100 * k;
for (int i = 0;i < n;i++) {
for (int j = 0;j < k;j++)
dis[i][j] = 1e16;
}
for (int i = 1;i <= m;i++) {
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
}
for (int i = 0;i < n;i++) {
int x = i / B;
int en = (i / B + 1) * B;
d[i] = 0;
for (int j = i + 1;j < min(n, en);j++)
d[j] = 1e18;
for (int j = i;j < min(n, en);j++) {
for (auto u : g[j]) {
d[u.f] = min(d[u.f], d[i] + u.s);
}
}
for (int j = en - 1;j >= max(i, en - k);j--)
dis[i][j % k] = d[j];
}
while (q--) {
int a, b;
cin >> a >> b;
if (a / B == b / B) {
for (int j = a;j <= b;j++)
d[j] = 1e18;
d[a] = 0;
for (int i = a;i < b;i++) {
for (auto u : g[i])
d[u.f] = min(d[u.f], d[i] + u.s);
}
if (d[b] >= 1e18)
cout << "-1\n";
else
cout << d[b] << '\n';
}
else {
int en = (a / B + 1) * B;
for (int j = en - 1;j >= en - k;j--)
d[j] = dis[a][j % k];
a = en - 1;
while (a / B != b / B) {
en = a + 1;
for (int j = en;j < en + k;j++)
d[j] = 1e18;
for (int j = en - 1;j >= en - k;j--) {
for (auto u : g[j])
d[u.f] = min(d[u.f], d[j] + u.s);
}
int ee = (en / B + 1) * B;
for (int j = ee - 1;j >= ee - k;j--)
d[j] = 1e18;
for (int j = en;j < en + k;j++) {
for (int i = 0;i < k;i++) {
int o = k - i;
d[ee - o] = min(d[ee - o], dis[j][i]);
}
}
a = ee - 1;
}
for (int i = en;i <= b;i++) {
for (auto u : g[i])
d[u.f] = min(d[u.f], d[i] + u.s);
}
if (d[b] >= 1e18)
cout << "-1\n";
else
cout << d[b] << '\n';
}
}
}
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:28:9: warning: unused variable 'x' [-Wunused-variable]
28 | int x = i / B;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
42 ms |
6748 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
67 ms |
8276 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
42 ms |
6748 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |