#pragma once
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
vector<int> U, vector<int> V, vector<ll> T) {
vector<ll> answer(q);
vector<vector<int>> queries(n);
for (int i = 0; i < q; ++i) {
queries[U[i]].push_back(i);
}
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; ++i) {
adj[A[i]].emplace_back(B[i], i);
adj[B[i]].emplace_back(A[i], i);
}
constexpr ll inf = 3e18;
auto dijkstra = [&](int source, ll s) -> vector<ll> {
vector<ll> dist(n, inf);
dist[source] = s;
vector<bool> used(n);
for (int _ = 0; _ < n; ++_) {
int v = -1;
for (int i = 0; i < n; ++i) {
if (!used[i] && (v == -1 || dist[i] < dist[v])) {
v = i;
}
}
used[v] = true;
for (auto [to, i] : adj[v]) {
ll d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S);
if (dist[to] > d) {
dist[to] = d;
}
}
}
return dist;
};
vector dist(n, vector<ll>(n));
for (int i = 0; i < n; ++i) {
dist[i] = dijkstra(i, 0);
}
for (int i = 0; i < q; ++i) {
vector<ll> d = dijkstra(U[i], T[i]);
answer[i] = d[V[i]] - T[i];
}
return answer;
vector dp(m, vector<ll>(n));
vector<ll> till(m);
for (int i = 0; i < n; ++i) {
vector<bool> broken(m);
for (int j = 0; j < m; ++j) {
ll s = j > 0 ? till[j - 1] + 1 : 0;
vector<ll> d = dijkstra(i, s);
for (int k = 0; k < m; ++k) {
}
}
}
}
Compilation message
escape_route.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
64980 KB |
Output is correct |
2 |
Correct |
35 ms |
64980 KB |
Output is correct |
3 |
Correct |
43 ms |
65056 KB |
Output is correct |
4 |
Correct |
25 ms |
64944 KB |
Output is correct |
5 |
Correct |
39 ms |
64944 KB |
Output is correct |
6 |
Correct |
32 ms |
65024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
9079 ms |
154964 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
64980 KB |
Output is correct |
2 |
Correct |
35 ms |
64980 KB |
Output is correct |
3 |
Correct |
43 ms |
65056 KB |
Output is correct |
4 |
Correct |
25 ms |
64944 KB |
Output is correct |
5 |
Correct |
39 ms |
64944 KB |
Output is correct |
6 |
Correct |
32 ms |
65024 KB |
Output is correct |
7 |
Execution timed out |
9079 ms |
154964 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
64980 KB |
Output is correct |
2 |
Correct |
35 ms |
64980 KB |
Output is correct |
3 |
Correct |
43 ms |
65056 KB |
Output is correct |
4 |
Correct |
25 ms |
64944 KB |
Output is correct |
5 |
Correct |
39 ms |
64944 KB |
Output is correct |
6 |
Correct |
32 ms |
65024 KB |
Output is correct |
7 |
Execution timed out |
9079 ms |
154964 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
64980 KB |
Output is correct |
2 |
Correct |
35 ms |
64980 KB |
Output is correct |
3 |
Correct |
43 ms |
65056 KB |
Output is correct |
4 |
Correct |
25 ms |
64944 KB |
Output is correct |
5 |
Correct |
39 ms |
64944 KB |
Output is correct |
6 |
Correct |
32 ms |
65024 KB |
Output is correct |
7 |
Execution timed out |
9079 ms |
154964 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |