# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
689368 |
2023-01-28T10:12:42 Z |
JooDdae |
Robot (JOI21_ho_t4) |
C++17 |
|
789 ms |
96972 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n, m, X[200200], Y[200200], C[200200], P[200200];
vector<array<int, 2>> v[100100];
list<array<int, 2>> l[100100];
bool chk[100100], chk2[100100];
ll d[200200][2][2], S[200200][2];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
priority_queue<array<ll, 5>, vector<array<ll, 5>>, greater<>> pq2;
int cnt, cur[200200][2];
ll mn[400400];
vector<array<int, 2>> v2[400400];
void update(int U) {
if(v2[U].empty()) return;
auto [x, y] = v2[U].back();
ll C = mn[U] + S[x][y] - P[x];
if(C < d[x][y][1]) d[x][y][1] = C, pq2.push({C, x, y, 1, U});
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++) {
cin >> X[i] >> Y[i] >> C[i] >> P[i];
v[X[i]].push_back({i, 0}), v[Y[i]].push_back({i, 1});
for(int j=0;j<2;j++) d[i][j][0] = d[i][j][1] = INF;
}
for(int i=1;i<=n;i++) {
auto &V = v[i];
sort(V.begin(), V.end(), [&](const array<int, 2> &a, const array<int, 2> &b) { return tie(C[a[0]], P[a[0]]) < tie(C[b[0]], P[b[0]]); });
for(auto x : V) l[i].push_back(x);
for(int j=0;j<V.size();j++) {
int k = j;
ll sum = P[V[j][0]];
while(k+1 < V.size() && C[V[j][0]] == C[V[k+1][0]]) sum += P[V[++k][0]];
for(int l=j;l<=k;l++) {
auto [x, y] = V[l];
S[x][y] = sum, cur[x][y] = cnt, v2[cnt].push_back({x, y});
}
j = k, cnt++;
}
}
fill(mn, mn+cnt, INF);
X[0] = Y[0] = 1, pq.push({0, 0, 0, 0});
while(!pq.empty()) {
auto [cost, id, k, type] = pq.top();
if(!pq2.empty() && pq2.top()[0] < cost) {
auto [cost, id, k, type, U] = pq2.top(); pq2.pop();
if(d[id][k][type] < cost || mn[U]+S[id][k]-P[id] != cost) continue;
pq.push({cost, id, k, type}), v2[U].pop_back();
update(U);
continue;
}
pq.pop();
if(d[id][k][type] < cost) continue;
int u = k ? X[id] : Y[id];
if(u == n) return cout << cost, 0;
if(type) {
while(!l[u].empty() && C[l[u].front()[0]] != C[id]) {
auto [x, y] = l[u].front(); l[u].pop_front();
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
while(!l[u].empty() && C[l[u].back()[0]] != C[id]) {
auto [x, y] = l[u].back(); l[u].pop_back();
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
if(!chk2[u]) {
for(auto [x, y] : l[u]) {
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
chk2[u] = 1;
}
continue;
}
if(!chk[u]) {
for(auto [x, y] : v[u]) {
ll C1 = cost + S[x][y] - P[x];
if(C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
ll C2 = cost + P[x];
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
chk[u] = 1;
}
int U = cur[id][!k];
if(v2[U].empty() || mn[U] <= cost-P[id]) continue;
mn[U] = min(mn[U], cost-P[id]);
update(U);
// for(auto [x, y] : v2[U]) if(x != id) {
// ll C = mn[U] + S[x][y] - P[x];
// if(C < d[x][y][1]) d[x][y][1] = C, pq.push({C, x, y, 1});
// }
}
cout << -1;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j=0;j<V.size();j++) {
| ~^~~~~~~~~
Main.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while(k+1 < V.size() && C[V[j][0]] == C[V[k+1][0]]) sum += P[V[++k][0]];
| ~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14460 KB |
Output is correct |
2 |
Correct |
7 ms |
14388 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
7 ms |
14528 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14804 KB |
Output is correct |
8 |
Correct |
8 ms |
14548 KB |
Output is correct |
9 |
Correct |
10 ms |
15188 KB |
Output is correct |
10 |
Correct |
12 ms |
15060 KB |
Output is correct |
11 |
Correct |
10 ms |
15188 KB |
Output is correct |
12 |
Correct |
10 ms |
15060 KB |
Output is correct |
13 |
Correct |
12 ms |
15132 KB |
Output is correct |
14 |
Correct |
10 ms |
15188 KB |
Output is correct |
15 |
Correct |
8 ms |
14676 KB |
Output is correct |
16 |
Correct |
11 ms |
14804 KB |
Output is correct |
17 |
Correct |
10 ms |
14932 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
15060 KB |
Output is correct |
20 |
Correct |
9 ms |
14744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
39164 KB |
Output is correct |
2 |
Correct |
92 ms |
26228 KB |
Output is correct |
3 |
Correct |
99 ms |
39812 KB |
Output is correct |
4 |
Correct |
68 ms |
29608 KB |
Output is correct |
5 |
Correct |
760 ms |
80072 KB |
Output is correct |
6 |
Correct |
668 ms |
78452 KB |
Output is correct |
7 |
Correct |
494 ms |
94584 KB |
Output is correct |
8 |
Correct |
472 ms |
57392 KB |
Output is correct |
9 |
Correct |
555 ms |
57576 KB |
Output is correct |
10 |
Correct |
388 ms |
50748 KB |
Output is correct |
11 |
Correct |
90 ms |
36036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14460 KB |
Output is correct |
2 |
Correct |
7 ms |
14388 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
7 ms |
14528 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14804 KB |
Output is correct |
8 |
Correct |
8 ms |
14548 KB |
Output is correct |
9 |
Correct |
10 ms |
15188 KB |
Output is correct |
10 |
Correct |
12 ms |
15060 KB |
Output is correct |
11 |
Correct |
10 ms |
15188 KB |
Output is correct |
12 |
Correct |
10 ms |
15060 KB |
Output is correct |
13 |
Correct |
12 ms |
15132 KB |
Output is correct |
14 |
Correct |
10 ms |
15188 KB |
Output is correct |
15 |
Correct |
8 ms |
14676 KB |
Output is correct |
16 |
Correct |
11 ms |
14804 KB |
Output is correct |
17 |
Correct |
10 ms |
14932 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
15060 KB |
Output is correct |
20 |
Correct |
9 ms |
14744 KB |
Output is correct |
21 |
Correct |
151 ms |
39164 KB |
Output is correct |
22 |
Correct |
92 ms |
26228 KB |
Output is correct |
23 |
Correct |
99 ms |
39812 KB |
Output is correct |
24 |
Correct |
68 ms |
29608 KB |
Output is correct |
25 |
Correct |
760 ms |
80072 KB |
Output is correct |
26 |
Correct |
668 ms |
78452 KB |
Output is correct |
27 |
Correct |
494 ms |
94584 KB |
Output is correct |
28 |
Correct |
472 ms |
57392 KB |
Output is correct |
29 |
Correct |
555 ms |
57576 KB |
Output is correct |
30 |
Correct |
388 ms |
50748 KB |
Output is correct |
31 |
Correct |
90 ms |
36036 KB |
Output is correct |
32 |
Correct |
165 ms |
77136 KB |
Output is correct |
33 |
Correct |
145 ms |
55740 KB |
Output is correct |
34 |
Correct |
214 ms |
54636 KB |
Output is correct |
35 |
Correct |
158 ms |
49144 KB |
Output is correct |
36 |
Correct |
371 ms |
62804 KB |
Output is correct |
37 |
Correct |
483 ms |
69416 KB |
Output is correct |
38 |
Correct |
492 ms |
96972 KB |
Output is correct |
39 |
Correct |
287 ms |
70480 KB |
Output is correct |
40 |
Correct |
510 ms |
59012 KB |
Output is correct |
41 |
Correct |
658 ms |
59296 KB |
Output is correct |
42 |
Correct |
758 ms |
73744 KB |
Output is correct |
43 |
Correct |
282 ms |
44236 KB |
Output is correct |
44 |
Correct |
196 ms |
60676 KB |
Output is correct |
45 |
Correct |
479 ms |
48820 KB |
Output is correct |
46 |
Correct |
286 ms |
45380 KB |
Output is correct |
47 |
Correct |
480 ms |
63452 KB |
Output is correct |
48 |
Correct |
789 ms |
79128 KB |
Output is correct |