# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
860499 |
2023-10-13T06:57:12 Z |
The_Samurai |
Toll (BOI17_toll) |
C++17 |
|
3000 ms |
5868 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m, k, q;
cin >> k >> n >> m >> q;
vector queries(n, vector<pair<int, int>>());
vector<int> ans(q);
vector<vector<pair<int, int>>> out(n);
while (m--) {
int u, v, t;
cin >> u >> v >> t;
out[u].emplace_back(v, t);
}
for (int i = 0; i < q; i++) {
int u, v;
cin >> u >> v;
queries[u].emplace_back(v, i);
}
vector dist(k, vector(n, inf));
for (int i = n - 1; i / k == (n - 1) / k; i--) dist[i % k][i] = 0;
for (int i = (n - 1) / k - 1; i >= 0; i--) {
int left = k * i, right = k * (i + 1) - 1;
vector new_dist(k, vector(n, inf));
for (int u = left; u <= right; u++) {
new_dist[u % k][u] = 0;
for (auto [v, t]: out[u]) {
for (int j = u; j < n; j++) {
new_dist[u % k][j] = min(new_dist[u % k][j], dist[v % k][j] + t);
}
}
for (auto [v, j]: queries[u]) {
ans[j] = new_dist[u % k][v];
}
}
dist = new_dist;
}
for (int i = 0; i < q; i++) cout << (ans[i] == inf ? -1 : ans[i]) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3076 ms |
5272 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3005 ms |
5868 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3076 ms |
5272 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |