#include "escape_route.h"
#include <cstring>
using namespace std;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
const int N = 90, M = N * (N - 1) / 2, Q = 3000000;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef vector<int> vi;
typedef vector<long long> vl;
unsigned int X;
int rand_() {
return (X *= 3) >> 1;
}
int ii[Q], jj[Q], hh[Q]; long long rr[Q];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ii[hh[j]] != ii[h] ? ii[hh[j]] - ii[h] : (rr[hh[j]] == rr[h] ? 0 : rr[hh[j]] < rr[h] ? -1 : 1);
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
long long ww[N][N], cc[N][N], dd1[N][N], dd2[N][N], dd[N]; char visited[N];
vl calculate_necessary_time(int n, int m, long long md, int q, vi uu_, vi vv_, vl ww_, vl cc_, vi ii_, vi jj_, vl rr_) {
for (int i = 0; i < n; i++)
memset(ww[i], 0x3f, n * sizeof *ww[i]);
for (int h = 0; h < m; h++) {
int u = uu_[h], v = vv_[h];
ww[u][v] = ww[v][u] = ww_[h], cc[u][v] = cc[v][u] = cc_[h] - ww_[h];
}
for (int t = 0; t < n; t++) {
memset(dd1[t], -1, n * sizeof *dd1[t]), dd1[t][t] = md;
for (int h = 0; h < n; h++) {
int j, j_ = -1;
for (j = 0; j < n; j++)
if (!visited[j] && (j_ == -1 || dd1[t][j_] < dd1[t][j]))
j_ = j;
j = j_;
visited[j] = 1;
long long d = dd1[t][j];
for (int i = 0; i < n; i++)
if (!visited[i] && ww[i][j] != INF)
dd1[t][i] = max(dd1[t][i], min(d - ww[i][j], cc[i][j]));
}
}
for (int s = 0; s < n; s++) {
memset(dd2[s], 0x3f, n * sizeof *dd2[s]), dd2[s][s] = 0;
memset(visited, 0, n * sizeof *visited);
for (int h = 0; h < n; h++) {
int i, i_ = -1;
for (i = 0; i < n; i++)
if (!visited[i] && (i_ == -1 || dd2[s][i_] > dd2[s][i]))
i_ = i;
i = i_;
visited[i] = 1;
long long d = dd2[s][i];
for (int j = 0; j < n; j++)
if (!visited[j] && ww[i][j] != INF)
dd2[s][j] = min(dd2[s][j], (d % md <= cc[i][j] ? d : (d + md - 1) / md * md) + ww[i][j]);
}
}
for (int h = 0; h < q; h++)
ii[h] = ii_[h], jj[h] = jj_[h], rr[h] = rr_[h];
for (int h = 0; h < q; h++)
hh[h] = h;
sort(hh, 0, q);
vl ans(q);
for (int h = 0, h_; h < q; h = h_) {
int i = ii[hh[h]];
h_ = h;
while (h_ < q && ii[hh[h_]] == i)
h_++;
for (int h1 = h; h1 < h_; h1++) {
int h1_ = hh[h1], j = jj[h1_];
long long r = rr[h1_];
memset(dd, 0x3f, n * sizeof *dd), dd[i] = r;
memset(visited, 0, n * sizeof *visited);
for (int h = 0; h < n; h++) {
int i, i_ = -1;
for (i = 0; i < n; i++)
if (!visited[i] && (i_ == -1 || dd[i_] > dd[i]))
i_ = i;
i = i_;
visited[i] = 1;
long long d = dd[i];
for (int j = 0; j < n; j++)
if (!visited[j] && ww[i][j] != INF)
dd[j] = min(dd[j], (d % md <= cc[i][j] ? d : (d + md - 1) / md * md) + ww[i][j]);
}
ans[h1_] = dd[j] - r;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
64972 KB |
Output is correct |
| 2 |
Correct |
36 ms |
65020 KB |
Output is correct |
| 3 |
Correct |
39 ms |
65024 KB |
Output is correct |
| 4 |
Correct |
26 ms |
65044 KB |
Output is correct |
| 5 |
Correct |
34 ms |
65028 KB |
Output is correct |
| 6 |
Correct |
31 ms |
64980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9076 ms |
129532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
64972 KB |
Output is correct |
| 2 |
Correct |
36 ms |
65020 KB |
Output is correct |
| 3 |
Correct |
39 ms |
65024 KB |
Output is correct |
| 4 |
Correct |
26 ms |
65044 KB |
Output is correct |
| 5 |
Correct |
34 ms |
65028 KB |
Output is correct |
| 6 |
Correct |
31 ms |
64980 KB |
Output is correct |
| 7 |
Execution timed out |
9076 ms |
129532 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
64972 KB |
Output is correct |
| 2 |
Correct |
36 ms |
65020 KB |
Output is correct |
| 3 |
Correct |
39 ms |
65024 KB |
Output is correct |
| 4 |
Correct |
26 ms |
65044 KB |
Output is correct |
| 5 |
Correct |
34 ms |
65028 KB |
Output is correct |
| 6 |
Correct |
31 ms |
64980 KB |
Output is correct |
| 7 |
Execution timed out |
9076 ms |
129532 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
64972 KB |
Output is correct |
| 2 |
Correct |
36 ms |
65020 KB |
Output is correct |
| 3 |
Correct |
39 ms |
65024 KB |
Output is correct |
| 4 |
Correct |
26 ms |
65044 KB |
Output is correct |
| 5 |
Correct |
34 ms |
65028 KB |
Output is correct |
| 6 |
Correct |
31 ms |
64980 KB |
Output is correct |
| 7 |
Execution timed out |
9076 ms |
129532 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
