| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 444777 |
2021-07-15T08:22:51 Z |
dutch |
Robot (JOI21_ho_t4) |
C++17 |
|
1103 ms |
85928 KB |
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 1e18;
class comp{
public:
bool operator()(array<int, 3> &x, array<int, 3> &y){ return x[0] > y[0]; }
};
map<int, int> d[LIM], s[LIM];
map<int, vector<array<int, 2>>> g[LIM];
priority_queue<array<int, 3>, vector<array<int, 3>>, comp> q;
void add(int i, int j, int k){
if(d[i][k] > j) q.push({d[i][k] = j, i, k});
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for(int i=0; i<m; ++i){
int u, v, c, w; cin >> u >> v >> c >> w;
--u, --v;
g[u][c].push_back({v, w});
g[v][c].push_back({u, w});
s[u][c] += w;
s[v][c] += w;
d[u][c] = d[v][c] = INF;
}
for(int u=0; u<n; ++u) d[u][0] = INF;
q.push({d[0][0] = 0, 0});
while(!q.empty()){
int dist = q.top()[0], u = q.top()[1], c = q.top()[2];
q.pop();
if(dist != d[u][c]) continue;
if(c){
for(auto &[v, w] : g[u][c])
if(s[u][c] - w >= 0)
add(v, dist + s[u][c] - w, 0);
}else{
for(auto &h : g[u])
for(auto &[v, w] : h.second){
add(v, dist + min(s[u][h.first] - w, w), 0);
add(v, dist, h.first);
}
}
}
cout << (d[n-1][0] == INF ? -1 : d[n-1][0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14324 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14448 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 7 |
Correct |
9 ms |
14656 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 9 |
Correct |
12 ms |
15056 KB |
Output is correct |
| 10 |
Correct |
12 ms |
14912 KB |
Output is correct |
| 11 |
Correct |
10 ms |
14796 KB |
Output is correct |
| 12 |
Correct |
9 ms |
14816 KB |
Output is correct |
| 13 |
Correct |
10 ms |
14924 KB |
Output is correct |
| 14 |
Correct |
10 ms |
14924 KB |
Output is correct |
| 15 |
Correct |
9 ms |
14656 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14744 KB |
Output is correct |
| 18 |
Correct |
9 ms |
14640 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14628 KB |
Output is correct |
| 20 |
Correct |
10 ms |
14668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
34536 KB |
Output is correct |
| 2 |
Correct |
108 ms |
25056 KB |
Output is correct |
| 3 |
Correct |
273 ms |
30944 KB |
Output is correct |
| 4 |
Correct |
170 ms |
28536 KB |
Output is correct |
| 5 |
Correct |
1095 ms |
85928 KB |
Output is correct |
| 6 |
Correct |
880 ms |
75724 KB |
Output is correct |
| 7 |
Correct |
476 ms |
58100 KB |
Output is correct |
| 8 |
Correct |
492 ms |
52484 KB |
Output is correct |
| 9 |
Correct |
530 ms |
52360 KB |
Output is correct |
| 10 |
Correct |
440 ms |
51120 KB |
Output is correct |
| 11 |
Correct |
195 ms |
40004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14324 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14448 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 7 |
Correct |
9 ms |
14656 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 9 |
Correct |
12 ms |
15056 KB |
Output is correct |
| 10 |
Correct |
12 ms |
14912 KB |
Output is correct |
| 11 |
Correct |
10 ms |
14796 KB |
Output is correct |
| 12 |
Correct |
9 ms |
14816 KB |
Output is correct |
| 13 |
Correct |
10 ms |
14924 KB |
Output is correct |
| 14 |
Correct |
10 ms |
14924 KB |
Output is correct |
| 15 |
Correct |
9 ms |
14656 KB |
Output is correct |
| 16 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14744 KB |
Output is correct |
| 18 |
Correct |
9 ms |
14640 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14628 KB |
Output is correct |
| 20 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 21 |
Correct |
286 ms |
34536 KB |
Output is correct |
| 22 |
Correct |
108 ms |
25056 KB |
Output is correct |
| 23 |
Correct |
273 ms |
30944 KB |
Output is correct |
| 24 |
Correct |
170 ms |
28536 KB |
Output is correct |
| 25 |
Correct |
1095 ms |
85928 KB |
Output is correct |
| 26 |
Correct |
880 ms |
75724 KB |
Output is correct |
| 27 |
Correct |
476 ms |
58100 KB |
Output is correct |
| 28 |
Correct |
492 ms |
52484 KB |
Output is correct |
| 29 |
Correct |
530 ms |
52360 KB |
Output is correct |
| 30 |
Correct |
440 ms |
51120 KB |
Output is correct |
| 31 |
Correct |
195 ms |
40004 KB |
Output is correct |
| 32 |
Correct |
173 ms |
25552 KB |
Output is correct |
| 33 |
Correct |
244 ms |
28856 KB |
Output is correct |
| 34 |
Correct |
598 ms |
50440 KB |
Output is correct |
| 35 |
Correct |
437 ms |
42552 KB |
Output is correct |
| 36 |
Correct |
395 ms |
51500 KB |
Output is correct |
| 37 |
Correct |
465 ms |
54088 KB |
Output is correct |
| 38 |
Correct |
522 ms |
64272 KB |
Output is correct |
| 39 |
Correct |
199 ms |
28172 KB |
Output is correct |
| 40 |
Correct |
519 ms |
52296 KB |
Output is correct |
| 41 |
Correct |
581 ms |
52396 KB |
Output is correct |
| 42 |
Correct |
687 ms |
64896 KB |
Output is correct |
| 43 |
Correct |
313 ms |
37996 KB |
Output is correct |
| 44 |
Correct |
590 ms |
39508 KB |
Output is correct |
| 45 |
Correct |
424 ms |
49164 KB |
Output is correct |
| 46 |
Correct |
355 ms |
49604 KB |
Output is correct |
| 47 |
Correct |
422 ms |
52644 KB |
Output is correct |
| 48 |
Correct |
1103 ms |
85896 KB |
Output is correct |
