# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
771244 |
2023-07-02T17:16:32 Z |
SamNguyen |
Robot (JOI21_ho_t4) |
C++14 |
|
145 ms |
22500 KB |
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const lli INF = 0x1f1f1f1f1f1f1f1f;
const int MAX_N = 1e5 + 7;
const int MAX_M = 2e5 + 7;
template <class T1, class T2>
inline constexpr bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
template <class T1, class T2>
inline constexpr bool maximise(T1 &x, T2 y) {
if (x < y) { x = y; return true; }
return false;
}
class Edge {
private:
int u, v, c;
lli w;
public:
Edge(int u = 0, int v = 0, int c = 0, lli w = 0): u(u), v(v), c(c), w(w) {}
inline lli cost() const { return w; }
inline pair<int, int> nodes() const { return make_pair(u, v); }
inline int other_node(int z) const { return u ^ v ^ z; }
inline int colour() const { return c; }
inline int get_node(bool is_rev) const { return is_rev ? v : u; }
inline bool is_start(int z) const { return z == u; }
};
int N, M;
Edge edge[MAX_M];
vector<int> adj[MAX_N];
void input() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int u, v, c; lli w;
cin >> u >> v >> c >> w;
edge[i] = Edge(u, v, c, w);
adj[u].push_back(i);
adj[v].push_back(i);
}
}
lli dist[MAX_N];
min_priority_queue<pair<lli, int>> pq;
lli sum_by_colour[MAX_M], min_by_colour[MAX_M];
lli solve() {
memset(dist, 0x1f, sizeof dist);
memset(sum_by_colour, 0, sizeof sum_by_colour);
memset(min_by_colour, 0x1f, sizeof min_by_colour);
auto relax = [&](int u, lli d) {
if (minimise(dist[u], d))
pq.emplace(d, u);
};
relax(1, 0);
lli ans = INF;
while (not pq.empty()) {
lli cur_dist; int u;
tie(cur_dist, u) = pq.top();
pq.pop();
if (u == N)
minimise(ans, cur_dist);
if (cur_dist > dist[u])
continue;
for (int j : adj[u]) {
int v = edge[j].other_node(u);
int c = edge[j].colour();
lli w = edge[j].cost();
sum_by_colour[c] += w;
minimise(min_by_colour[c], dist[v]);
}
for (int j : adj[u]) {
int v = edge[j].other_node(u);
int c = edge[j].colour();
lli w = edge[j].cost();
relax(v, cur_dist + min(w, sum_by_colour[c] - w));
relax(v, min_by_colour[c] + sum_by_colour[c] - w);
}
for (int j : adj[u]) {
int c = edge[j].colour();
sum_by_colour[c] = 0;
min_by_colour[c] = INF;
}
}
if (ans >= INF)
ans = -1;
return ans;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
input();
cout << solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
11220 KB |
Output is correct |
2 |
Correct |
5 ms |
11276 KB |
Output is correct |
3 |
Correct |
5 ms |
11220 KB |
Output is correct |
4 |
Correct |
4 ms |
11220 KB |
Output is correct |
5 |
Correct |
4 ms |
11220 KB |
Output is correct |
6 |
Correct |
5 ms |
11220 KB |
Output is correct |
7 |
Correct |
6 ms |
11300 KB |
Output is correct |
8 |
Correct |
5 ms |
11220 KB |
Output is correct |
9 |
Correct |
5 ms |
11348 KB |
Output is correct |
10 |
Correct |
5 ms |
11348 KB |
Output is correct |
11 |
Correct |
5 ms |
11348 KB |
Output is correct |
12 |
Correct |
5 ms |
11220 KB |
Output is correct |
13 |
Correct |
5 ms |
11264 KB |
Output is correct |
14 |
Correct |
5 ms |
11348 KB |
Output is correct |
15 |
Correct |
5 ms |
11196 KB |
Output is correct |
16 |
Correct |
7 ms |
11220 KB |
Output is correct |
17 |
Correct |
7 ms |
11220 KB |
Output is correct |
18 |
Correct |
5 ms |
11220 KB |
Output is correct |
19 |
Correct |
5 ms |
11220 KB |
Output is correct |
20 |
Correct |
5 ms |
11220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
12992 KB |
Output is correct |
2 |
Correct |
19 ms |
12160 KB |
Output is correct |
3 |
Correct |
54 ms |
13720 KB |
Output is correct |
4 |
Correct |
29 ms |
12724 KB |
Output is correct |
5 |
Correct |
112 ms |
17256 KB |
Output is correct |
6 |
Correct |
98 ms |
21568 KB |
Output is correct |
7 |
Correct |
85 ms |
21280 KB |
Output is correct |
8 |
Correct |
89 ms |
19448 KB |
Output is correct |
9 |
Correct |
93 ms |
19400 KB |
Output is correct |
10 |
Correct |
54 ms |
16624 KB |
Output is correct |
11 |
Correct |
45 ms |
15580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
11220 KB |
Output is correct |
2 |
Correct |
5 ms |
11276 KB |
Output is correct |
3 |
Correct |
5 ms |
11220 KB |
Output is correct |
4 |
Correct |
4 ms |
11220 KB |
Output is correct |
5 |
Correct |
4 ms |
11220 KB |
Output is correct |
6 |
Correct |
5 ms |
11220 KB |
Output is correct |
7 |
Correct |
6 ms |
11300 KB |
Output is correct |
8 |
Correct |
5 ms |
11220 KB |
Output is correct |
9 |
Correct |
5 ms |
11348 KB |
Output is correct |
10 |
Correct |
5 ms |
11348 KB |
Output is correct |
11 |
Correct |
5 ms |
11348 KB |
Output is correct |
12 |
Correct |
5 ms |
11220 KB |
Output is correct |
13 |
Correct |
5 ms |
11264 KB |
Output is correct |
14 |
Correct |
5 ms |
11348 KB |
Output is correct |
15 |
Correct |
5 ms |
11196 KB |
Output is correct |
16 |
Correct |
7 ms |
11220 KB |
Output is correct |
17 |
Correct |
7 ms |
11220 KB |
Output is correct |
18 |
Correct |
5 ms |
11220 KB |
Output is correct |
19 |
Correct |
5 ms |
11220 KB |
Output is correct |
20 |
Correct |
5 ms |
11220 KB |
Output is correct |
21 |
Correct |
38 ms |
12992 KB |
Output is correct |
22 |
Correct |
19 ms |
12160 KB |
Output is correct |
23 |
Correct |
54 ms |
13720 KB |
Output is correct |
24 |
Correct |
29 ms |
12724 KB |
Output is correct |
25 |
Correct |
112 ms |
17256 KB |
Output is correct |
26 |
Correct |
98 ms |
21568 KB |
Output is correct |
27 |
Correct |
85 ms |
21280 KB |
Output is correct |
28 |
Correct |
89 ms |
19448 KB |
Output is correct |
29 |
Correct |
93 ms |
19400 KB |
Output is correct |
30 |
Correct |
54 ms |
16624 KB |
Output is correct |
31 |
Correct |
45 ms |
15580 KB |
Output is correct |
32 |
Correct |
52 ms |
17100 KB |
Output is correct |
33 |
Correct |
53 ms |
16688 KB |
Output is correct |
34 |
Correct |
76 ms |
18628 KB |
Output is correct |
35 |
Correct |
60 ms |
17632 KB |
Output is correct |
36 |
Correct |
75 ms |
18512 KB |
Output is correct |
37 |
Correct |
105 ms |
19616 KB |
Output is correct |
38 |
Correct |
82 ms |
21044 KB |
Output is correct |
39 |
Correct |
69 ms |
18512 KB |
Output is correct |
40 |
Correct |
101 ms |
20684 KB |
Output is correct |
41 |
Correct |
124 ms |
20888 KB |
Output is correct |
42 |
Correct |
114 ms |
20852 KB |
Output is correct |
43 |
Correct |
43 ms |
16000 KB |
Output is correct |
44 |
Correct |
71 ms |
19592 KB |
Output is correct |
45 |
Correct |
83 ms |
18736 KB |
Output is correct |
46 |
Correct |
68 ms |
18016 KB |
Output is correct |
47 |
Correct |
89 ms |
20336 KB |
Output is correct |
48 |
Correct |
145 ms |
22500 KB |
Output is correct |