# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1081507 |
2024-08-30T06:33:34 Z |
Pannda |
Robot (JOI21_ho_t4) |
C++17 |
|
427 ms |
104868 KB |
#include <bits/stdc++.h>
using namespace std;
template <class T>
vector<T> dijkstra(const vector<vector<pair<int, T>>> &adj, vector<T> dist) {
int n = adj.size();
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
for (int u = 0; u < n; u++) {
pq.push({dist[u], u});
}
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
struct Edge {
int v, color, cost;
};
vector<vector<Edge>> edges(n);
vector<vector<int>> colors(n);
for (int i = 0; i < m; i++) {
int u, v, color, cost;
cin >> u >> v >> color >> cost;
u--; v--;
edges[u].push_back({v, color, cost});
edges[v].push_back({u, color, cost});
colors[u].push_back(color);
colors[v].push_back(color);
}
for (int u = 0; u < n; u++) {
sort(colors[u].begin(), colors[u].end());
colors[u].resize(unique(colors[u].begin(), colors[u].end()) - colors[u].begin());
}
auto f = [&](int u, int color) -> int {
int i = lower_bound(colors[u].begin(), colors[u].end(), color) - colors[u].begin();
assert(i < colors[u].size());
return i;
};
vector<vector<long long>> sum(n);
vector<vector<int>> id(n);
int tim = n;
for (int u = 0; u < n; u++) {
sum[u].resize(colors[u].size(), 0);
for (auto [v, color, cost] : edges[u]) {
sum[u][f(u, color)] += cost;
}
id[u].resize(colors[u].size());
iota(id[u].begin(), id[u].end(), tim);
tim += colors[u].size();
}
vector<vector<pair<int, long long>>> adj(tim);
for (int u = 0; u < n; u++) {
for (auto [v, color, cost] : edges[u]) {
// (u) -> (v) + cost;
// (u) -> (v) + sum[f(u, color)][i] - cost
// (u) -> (v, color) + 0
// (u, color) -> (v) + sum[u][f(u, color)] - cost
int i = f(u, color);
int j = f(v, color);
adj[u].push_back({v, cost});
adj[u].push_back({v, sum[u][i] - cost});
adj[u].push_back({ id[v][j], 0 });
adj[id[u][i]].push_back({v, sum[u][i] - cost});
}
}
const long long INF = 4e18;
vector<long long> dist(tim, INF);
dist[0] = 0;
dist = dijkstra(adj, dist);
if (dist[n - 1] == INF) {
cout << -1 << '\n';
} else {
cout << dist[n - 1] << '\n';
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp: In lambda function:
Main.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | assert(i < colors[u].size());
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
596 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
748 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
1428 KB |
Output is correct |
10 |
Correct |
2 ms |
1372 KB |
Output is correct |
11 |
Correct |
2 ms |
1116 KB |
Output is correct |
12 |
Correct |
2 ms |
1116 KB |
Output is correct |
13 |
Correct |
2 ms |
1116 KB |
Output is correct |
14 |
Correct |
2 ms |
1116 KB |
Output is correct |
15 |
Correct |
1 ms |
860 KB |
Output is correct |
16 |
Correct |
3 ms |
1116 KB |
Output is correct |
17 |
Correct |
2 ms |
1116 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
19 |
Correct |
2 ms |
860 KB |
Output is correct |
20 |
Correct |
2 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
31428 KB |
Output is correct |
2 |
Correct |
47 ms |
15568 KB |
Output is correct |
3 |
Correct |
100 ms |
37832 KB |
Output is correct |
4 |
Correct |
62 ms |
21960 KB |
Output is correct |
5 |
Correct |
383 ms |
91256 KB |
Output is correct |
6 |
Correct |
308 ms |
84068 KB |
Output is correct |
7 |
Correct |
204 ms |
81320 KB |
Output is correct |
8 |
Correct |
305 ms |
81348 KB |
Output is correct |
9 |
Correct |
297 ms |
81408 KB |
Output is correct |
10 |
Correct |
178 ms |
55992 KB |
Output is correct |
11 |
Correct |
153 ms |
50372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
596 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
748 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
1428 KB |
Output is correct |
10 |
Correct |
2 ms |
1372 KB |
Output is correct |
11 |
Correct |
2 ms |
1116 KB |
Output is correct |
12 |
Correct |
2 ms |
1116 KB |
Output is correct |
13 |
Correct |
2 ms |
1116 KB |
Output is correct |
14 |
Correct |
2 ms |
1116 KB |
Output is correct |
15 |
Correct |
1 ms |
860 KB |
Output is correct |
16 |
Correct |
3 ms |
1116 KB |
Output is correct |
17 |
Correct |
2 ms |
1116 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
19 |
Correct |
2 ms |
860 KB |
Output is correct |
20 |
Correct |
2 ms |
1368 KB |
Output is correct |
21 |
Correct |
98 ms |
31428 KB |
Output is correct |
22 |
Correct |
47 ms |
15568 KB |
Output is correct |
23 |
Correct |
100 ms |
37832 KB |
Output is correct |
24 |
Correct |
62 ms |
21960 KB |
Output is correct |
25 |
Correct |
383 ms |
91256 KB |
Output is correct |
26 |
Correct |
308 ms |
84068 KB |
Output is correct |
27 |
Correct |
204 ms |
81320 KB |
Output is correct |
28 |
Correct |
305 ms |
81348 KB |
Output is correct |
29 |
Correct |
297 ms |
81408 KB |
Output is correct |
30 |
Correct |
178 ms |
55992 KB |
Output is correct |
31 |
Correct |
153 ms |
50372 KB |
Output is correct |
32 |
Correct |
89 ms |
38796 KB |
Output is correct |
33 |
Correct |
111 ms |
37204 KB |
Output is correct |
34 |
Correct |
201 ms |
54308 KB |
Output is correct |
35 |
Correct |
168 ms |
46656 KB |
Output is correct |
36 |
Correct |
190 ms |
64068 KB |
Output is correct |
37 |
Correct |
215 ms |
71612 KB |
Output is correct |
38 |
Correct |
219 ms |
81108 KB |
Output is correct |
39 |
Correct |
121 ms |
50112 KB |
Output is correct |
40 |
Correct |
291 ms |
82628 KB |
Output is correct |
41 |
Correct |
415 ms |
82836 KB |
Output is correct |
42 |
Correct |
306 ms |
81600 KB |
Output is correct |
43 |
Correct |
122 ms |
37716 KB |
Output is correct |
44 |
Correct |
170 ms |
58056 KB |
Output is correct |
45 |
Correct |
274 ms |
70340 KB |
Output is correct |
46 |
Correct |
222 ms |
69316 KB |
Output is correct |
47 |
Correct |
217 ms |
68780 KB |
Output is correct |
48 |
Correct |
427 ms |
104868 KB |
Output is correct |