#include "escape_route.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define int long long
#define i32 int32_t
const int INF = 1e18;
const int NN = 91;
int d[NN][NN], g[NN][NN];
int de[NN][NN][NN], used[NN];
vector<int> p[NN];
vector<int> calculate_necessary_time(
i32 n, i32 m, int S, i32 q, vector<i32> a, vector<i32> b,
vector<int> l, vector<int> c, vector<i32> u,
vector<i32> v, vector<int> T) {
memset(g, -1, sizeof g);
for(int i=0;i<m;i++){
g[a[i]][b[i]] =
g[b[i]][a[i]] = i;
p[a[i]].push_back(i);
p[b[i]].push_back(i);
}
auto go = [&](int i, int* d){
memset(used, 0, sizeof used);
while(~i){
used[i] = 1;
int t=-1;
for(int j=0;j<n;j++){
if(used[j]) continue;
if(~g[i][j]){
int k=g[i][j];
if(d[i]%S + l[k] <= c[k]){
d[j] = min(d[j], d[i] + l[k]);
} else {
d[j] = min(d[j], d[i] + (S - d[i]%S) + l[k]);
}
}
if(d[j] < INF && (t == -1 || d[j] < d[t])) t = j;
}
i = t;
}
};
//~ cout<<d[0][0]<<"\n"<<INF<<"\n";
for(int i=0;i<NN;i++){
for(int j=0;j<NN;j++){
for(int k=0;k<NN;k++){
de[i][j][k] = INF;
} d[i][j] = INF;
}
}
for(int i=0;i<n;i++){
d[i][i] = 0;
go(i, d[i]);
sort(p[i].begin(), p[i].end(), [&](int i, int j){
return c[i] - l[i] > c[j] - l[j];
});
for(int j=0;j<(int)p[i].size();j++){
de[j][i][i] = c[p[i][j]] - l[p[i][j]];
go(i, de[j][i]);
for(int k=0;k<n;k++){
if(de[j][i][k] >= S) de[j][i][k] = INF;
else de[j][i][k] -= (c[p[i][j]] - l[p[i][j]]);
}
}
}
vector<vector<int>> qq(n);
vector<int> res(q);
for(int i=0;i<q;i++){
qq[u[i]].push_back(i);
res[i] = INF;
}
for(int i=0;i<n;i++){
sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
return (T[i] < T[j]);
});
vector<int> cnt(n), D(n, INF), cur(n, -1);
D[i] = 0;
if(!p[i].empty()) cur[i] = c[p[i][0]] - l[p[i][0]];
while(!qq[i].empty()){
int j = max_element(cur.begin(), cur.end()) - cur.begin();
while(!qq[i].empty() && T[qq[i].back()] > cur[j]){
int in = qq[i].back(); qq[i].pop_back();
for(int g=0;g<n;g++){
if(D[g] == INF) continue;
res[in] = min(res[in], D[g] +
(g != v[in] ? (S - D[g] - T[in]) : 0ll) + d[g][v[in]]);
}
}
if(cur[j] < 0) break;
for(int g=0;g<n;g++){
if(D[g] > D[j] + de[cnt[j]][j][g]){
D[g] = D[j] + de[cnt[j]][j][g];
if(cnt[g] < (int)p[g].size()){
cur[g] = c[p[g][cnt[g]]] - l[p[g][cnt[g]]] - D[g];
}
}
}
cnt[j]++;
if(cnt[j] < (int)p[j].size()){
cur[j] = c[p[j][cnt[j]]] - l[p[j][cnt[j]]] - D[j];
} else {
cur[j] = -1;
}
}
//~ cout<<"here"<<endl;
} return res;
}
/*
4 5 20 1
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 7
4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
64972 KB |
Output is correct |
2 |
Correct |
31 ms |
64992 KB |
Output is correct |
3 |
Correct |
53 ms |
65092 KB |
Output is correct |
4 |
Correct |
32 ms |
65036 KB |
Output is correct |
5 |
Correct |
33 ms |
64956 KB |
Output is correct |
6 |
Correct |
27 ms |
64956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1564 ms |
112156 KB |
Output is correct |
2 |
Correct |
1571 ms |
126224 KB |
Output is correct |
3 |
Correct |
1464 ms |
117944 KB |
Output is correct |
4 |
Correct |
1626 ms |
127336 KB |
Output is correct |
5 |
Correct |
1607 ms |
127392 KB |
Output is correct |
6 |
Correct |
28 ms |
64972 KB |
Output is correct |
7 |
Correct |
1486 ms |
158812 KB |
Output is correct |
8 |
Correct |
1374 ms |
200404 KB |
Output is correct |
9 |
Correct |
1488 ms |
154872 KB |
Output is correct |
10 |
Correct |
1588 ms |
187416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
64972 KB |
Output is correct |
2 |
Correct |
31 ms |
64992 KB |
Output is correct |
3 |
Correct |
53 ms |
65092 KB |
Output is correct |
4 |
Correct |
32 ms |
65036 KB |
Output is correct |
5 |
Correct |
33 ms |
64956 KB |
Output is correct |
6 |
Correct |
27 ms |
64956 KB |
Output is correct |
7 |
Correct |
1564 ms |
112156 KB |
Output is correct |
8 |
Correct |
1571 ms |
126224 KB |
Output is correct |
9 |
Correct |
1464 ms |
117944 KB |
Output is correct |
10 |
Correct |
1626 ms |
127336 KB |
Output is correct |
11 |
Correct |
1607 ms |
127392 KB |
Output is correct |
12 |
Correct |
28 ms |
64972 KB |
Output is correct |
13 |
Correct |
1486 ms |
158812 KB |
Output is correct |
14 |
Correct |
1374 ms |
200404 KB |
Output is correct |
15 |
Correct |
1488 ms |
154872 KB |
Output is correct |
16 |
Correct |
1588 ms |
187416 KB |
Output is correct |
17 |
Correct |
1417 ms |
158636 KB |
Output is correct |
18 |
Correct |
1460 ms |
158740 KB |
Output is correct |
19 |
Correct |
1522 ms |
182176 KB |
Output is correct |
20 |
Correct |
1415 ms |
162516 KB |
Output is correct |
21 |
Correct |
1530 ms |
191664 KB |
Output is correct |
22 |
Correct |
1550 ms |
185672 KB |
Output is correct |
23 |
Correct |
1447 ms |
159200 KB |
Output is correct |
24 |
Correct |
1427 ms |
196832 KB |
Output is correct |
25 |
Correct |
1471 ms |
155932 KB |
Output is correct |
26 |
Correct |
1545 ms |
185080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
64972 KB |
Output is correct |
2 |
Correct |
31 ms |
64992 KB |
Output is correct |
3 |
Correct |
53 ms |
65092 KB |
Output is correct |
4 |
Correct |
32 ms |
65036 KB |
Output is correct |
5 |
Correct |
33 ms |
64956 KB |
Output is correct |
6 |
Correct |
27 ms |
64956 KB |
Output is correct |
7 |
Correct |
1564 ms |
112156 KB |
Output is correct |
8 |
Correct |
1571 ms |
126224 KB |
Output is correct |
9 |
Correct |
1464 ms |
117944 KB |
Output is correct |
10 |
Correct |
1626 ms |
127336 KB |
Output is correct |
11 |
Correct |
1607 ms |
127392 KB |
Output is correct |
12 |
Correct |
28 ms |
64972 KB |
Output is correct |
13 |
Correct |
1486 ms |
158812 KB |
Output is correct |
14 |
Correct |
1374 ms |
200404 KB |
Output is correct |
15 |
Correct |
1488 ms |
154872 KB |
Output is correct |
16 |
Correct |
1588 ms |
187416 KB |
Output is correct |
17 |
Correct |
1417 ms |
158636 KB |
Output is correct |
18 |
Correct |
1460 ms |
158740 KB |
Output is correct |
19 |
Correct |
1522 ms |
182176 KB |
Output is correct |
20 |
Correct |
1415 ms |
162516 KB |
Output is correct |
21 |
Correct |
1530 ms |
191664 KB |
Output is correct |
22 |
Correct |
1550 ms |
185672 KB |
Output is correct |
23 |
Correct |
1447 ms |
159200 KB |
Output is correct |
24 |
Correct |
1427 ms |
196832 KB |
Output is correct |
25 |
Correct |
1471 ms |
155932 KB |
Output is correct |
26 |
Correct |
1545 ms |
185080 KB |
Output is correct |
27 |
Correct |
1765 ms |
156892 KB |
Output is correct |
28 |
Correct |
1761 ms |
155636 KB |
Output is correct |
29 |
Correct |
1838 ms |
176412 KB |
Output is correct |
30 |
Correct |
1701 ms |
159636 KB |
Output is correct |
31 |
Correct |
1815 ms |
184704 KB |
Output is correct |
32 |
Correct |
1812 ms |
170576 KB |
Output is correct |
33 |
Correct |
1486 ms |
181488 KB |
Output is correct |
34 |
Correct |
1723 ms |
155404 KB |
Output is correct |
35 |
Correct |
1795 ms |
168300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
64972 KB |
Output is correct |
2 |
Correct |
31 ms |
64992 KB |
Output is correct |
3 |
Correct |
53 ms |
65092 KB |
Output is correct |
4 |
Correct |
32 ms |
65036 KB |
Output is correct |
5 |
Correct |
33 ms |
64956 KB |
Output is correct |
6 |
Correct |
27 ms |
64956 KB |
Output is correct |
7 |
Correct |
1564 ms |
112156 KB |
Output is correct |
8 |
Correct |
1571 ms |
126224 KB |
Output is correct |
9 |
Correct |
1464 ms |
117944 KB |
Output is correct |
10 |
Correct |
1626 ms |
127336 KB |
Output is correct |
11 |
Correct |
1607 ms |
127392 KB |
Output is correct |
12 |
Correct |
28 ms |
64972 KB |
Output is correct |
13 |
Correct |
1486 ms |
158812 KB |
Output is correct |
14 |
Correct |
1374 ms |
200404 KB |
Output is correct |
15 |
Correct |
1488 ms |
154872 KB |
Output is correct |
16 |
Correct |
1588 ms |
187416 KB |
Output is correct |
17 |
Correct |
1417 ms |
158636 KB |
Output is correct |
18 |
Correct |
1460 ms |
158740 KB |
Output is correct |
19 |
Correct |
1522 ms |
182176 KB |
Output is correct |
20 |
Correct |
1415 ms |
162516 KB |
Output is correct |
21 |
Correct |
1530 ms |
191664 KB |
Output is correct |
22 |
Correct |
1550 ms |
185672 KB |
Output is correct |
23 |
Correct |
1447 ms |
159200 KB |
Output is correct |
24 |
Correct |
1427 ms |
196832 KB |
Output is correct |
25 |
Correct |
1471 ms |
155932 KB |
Output is correct |
26 |
Correct |
1545 ms |
185080 KB |
Output is correct |
27 |
Correct |
1765 ms |
156892 KB |
Output is correct |
28 |
Correct |
1761 ms |
155636 KB |
Output is correct |
29 |
Correct |
1838 ms |
176412 KB |
Output is correct |
30 |
Correct |
1701 ms |
159636 KB |
Output is correct |
31 |
Correct |
1815 ms |
184704 KB |
Output is correct |
32 |
Correct |
1812 ms |
170576 KB |
Output is correct |
33 |
Correct |
1486 ms |
181488 KB |
Output is correct |
34 |
Correct |
1723 ms |
155404 KB |
Output is correct |
35 |
Correct |
1795 ms |
168300 KB |
Output is correct |
36 |
Correct |
2513 ms |
157216 KB |
Output is correct |
37 |
Correct |
2484 ms |
155724 KB |
Output is correct |
38 |
Correct |
2346 ms |
159720 KB |
Output is correct |
39 |
Correct |
2506 ms |
186780 KB |
Output is correct |
40 |
Correct |
2540 ms |
188060 KB |
Output is correct |
41 |
Correct |
1579 ms |
198380 KB |
Output is correct |
42 |
Correct |
2460 ms |
157136 KB |
Output is correct |
43 |
Correct |
2459 ms |
155996 KB |
Output is correct |