# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
652544 |
2022-10-22T23:01:59 Z |
ymm |
Robot (JOI21_ho_t4) |
C++17 |
|
1205 ms |
109576 KB |
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const ll inf = 1e17;
const int N = 100'010;
map<int, ll> sum[N];
map<int, vector<pll>> colA[N];
map<int, ll> dis[N];
vector<tuple<int,int,ll,ll>> A[N];
int n, m;
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,m) {
int v, u, c, w;
cin >> v >> u >> c >> w;
--v; --u;
A[v].push_back({u,c,w,0});
A[u].push_back({v,c,w,0});
sum[v][c] += w;
sum[u][c] += w;
}
Loop (v,0,n) {
for (auto &[u, c, w1, w2] : A[v]) {
w2 = sum[v][c] - w1;
colA[v][c].push_back({u,w2});
dis[v][c] = inf;
}
dis[v][-1] = inf;
}
set<tuple<ll,int,int>> s = {{0, -1, 0}};
dis[0][-1] = 0;
while (s.size()) {
auto [d, c, v] = *s.begin();
s.erase(s.begin());
if (c == -1) {
for (auto [u, c, w1, w2] : A[v]) {
ll w = min(w1, w2);
if (d + w < dis[u][-1]) {
s.erase({dis[u][-1], -1, u});
dis[u][-1] = d+w;
s.insert({dis[u][-1], -1, u});
}
if (d < dis[u][c]) {
s.erase({dis[u][c], c, u});
dis[u][c] = d;
s.insert({dis[u][c], c, u});
}
}
} else {
for (auto [u, w] : colA[v][c]) {
if (d + w < dis[u][-1]) {
s.erase({dis[u][-1], -1, u});
dis[u][-1] = d+w;
s.insert({dis[u][-1], -1, u});
}
}
}
}
cout << (dis[n-1][-1] == inf? -1: dis[n-1][-1]) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16724 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16760 KB |
Output is correct |
4 |
Correct |
8 ms |
16760 KB |
Output is correct |
5 |
Correct |
8 ms |
16724 KB |
Output is correct |
6 |
Correct |
8 ms |
16724 KB |
Output is correct |
7 |
Correct |
10 ms |
17004 KB |
Output is correct |
8 |
Correct |
9 ms |
16796 KB |
Output is correct |
9 |
Correct |
13 ms |
17620 KB |
Output is correct |
10 |
Correct |
13 ms |
17564 KB |
Output is correct |
11 |
Correct |
10 ms |
17364 KB |
Output is correct |
12 |
Correct |
11 ms |
17276 KB |
Output is correct |
13 |
Correct |
11 ms |
17364 KB |
Output is correct |
14 |
Correct |
10 ms |
17364 KB |
Output is correct |
15 |
Correct |
9 ms |
17108 KB |
Output is correct |
16 |
Correct |
11 ms |
17280 KB |
Output is correct |
17 |
Correct |
10 ms |
17284 KB |
Output is correct |
18 |
Correct |
10 ms |
16980 KB |
Output is correct |
19 |
Correct |
11 ms |
17108 KB |
Output is correct |
20 |
Correct |
10 ms |
17108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
45228 KB |
Output is correct |
2 |
Correct |
103 ms |
31536 KB |
Output is correct |
3 |
Correct |
212 ms |
44776 KB |
Output is correct |
4 |
Correct |
133 ms |
36100 KB |
Output is correct |
5 |
Correct |
1092 ms |
108972 KB |
Output is correct |
6 |
Correct |
898 ms |
96732 KB |
Output is correct |
7 |
Correct |
348 ms |
80204 KB |
Output is correct |
8 |
Correct |
385 ms |
70620 KB |
Output is correct |
9 |
Correct |
401 ms |
70600 KB |
Output is correct |
10 |
Correct |
354 ms |
66584 KB |
Output is correct |
11 |
Correct |
142 ms |
50140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16724 KB |
Output is correct |
2 |
Correct |
8 ms |
16724 KB |
Output is correct |
3 |
Correct |
8 ms |
16760 KB |
Output is correct |
4 |
Correct |
8 ms |
16760 KB |
Output is correct |
5 |
Correct |
8 ms |
16724 KB |
Output is correct |
6 |
Correct |
8 ms |
16724 KB |
Output is correct |
7 |
Correct |
10 ms |
17004 KB |
Output is correct |
8 |
Correct |
9 ms |
16796 KB |
Output is correct |
9 |
Correct |
13 ms |
17620 KB |
Output is correct |
10 |
Correct |
13 ms |
17564 KB |
Output is correct |
11 |
Correct |
10 ms |
17364 KB |
Output is correct |
12 |
Correct |
11 ms |
17276 KB |
Output is correct |
13 |
Correct |
11 ms |
17364 KB |
Output is correct |
14 |
Correct |
10 ms |
17364 KB |
Output is correct |
15 |
Correct |
9 ms |
17108 KB |
Output is correct |
16 |
Correct |
11 ms |
17280 KB |
Output is correct |
17 |
Correct |
10 ms |
17284 KB |
Output is correct |
18 |
Correct |
10 ms |
16980 KB |
Output is correct |
19 |
Correct |
11 ms |
17108 KB |
Output is correct |
20 |
Correct |
10 ms |
17108 KB |
Output is correct |
21 |
Correct |
208 ms |
45228 KB |
Output is correct |
22 |
Correct |
103 ms |
31536 KB |
Output is correct |
23 |
Correct |
212 ms |
44776 KB |
Output is correct |
24 |
Correct |
133 ms |
36100 KB |
Output is correct |
25 |
Correct |
1092 ms |
108972 KB |
Output is correct |
26 |
Correct |
898 ms |
96732 KB |
Output is correct |
27 |
Correct |
348 ms |
80204 KB |
Output is correct |
28 |
Correct |
385 ms |
70620 KB |
Output is correct |
29 |
Correct |
401 ms |
70600 KB |
Output is correct |
30 |
Correct |
354 ms |
66584 KB |
Output is correct |
31 |
Correct |
142 ms |
50140 KB |
Output is correct |
32 |
Correct |
130 ms |
38256 KB |
Output is correct |
33 |
Correct |
190 ms |
39328 KB |
Output is correct |
34 |
Correct |
439 ms |
64220 KB |
Output is correct |
35 |
Correct |
379 ms |
53776 KB |
Output is correct |
36 |
Correct |
360 ms |
64312 KB |
Output is correct |
37 |
Correct |
390 ms |
70132 KB |
Output is correct |
38 |
Correct |
493 ms |
79960 KB |
Output is correct |
39 |
Correct |
157 ms |
44936 KB |
Output is correct |
40 |
Correct |
409 ms |
72032 KB |
Output is correct |
41 |
Correct |
423 ms |
72060 KB |
Output is correct |
42 |
Correct |
513 ms |
82688 KB |
Output is correct |
43 |
Correct |
218 ms |
48716 KB |
Output is correct |
44 |
Correct |
364 ms |
59040 KB |
Output is correct |
45 |
Correct |
336 ms |
64580 KB |
Output is correct |
46 |
Correct |
286 ms |
63676 KB |
Output is correct |
47 |
Correct |
333 ms |
68860 KB |
Output is correct |
48 |
Correct |
1205 ms |
109576 KB |
Output is correct |