# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
934282 |
2024-02-27T05:52:24 Z |
Pring |
Robot (JOI21_ho_t4) |
C++17 |
|
1398 ms |
132588 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 200005, INF = 3.9e18;
int n, m, a[MXN], b[MXN], c[MXN], p[MXN];
int C;
map<int, vector<pii>> Mv[MXN];
map<int, int> Mi[MXN];
map<int, pii> Mid;
map<pii, int> Mp;
vector<int> eid[MXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<int> dis;
int DIJKSTRA(int sr, int to) {
auto UPDATE1 = [&](int id, int len) -> void {
debug(id);
for (auto &e : eid[id]) {
int i = a[e] ^ b[e] ^ id, clr = c[e];
// debug(e, i, clr, Mp[mp(i, clr)]);
debug(p[e], Mi[id][clr] - p[e]);
debug(len + min(p[e], Mi[id][clr] - p[e]), i);
pq.push(mp(len + min(p[e], Mi[id][clr] - p[e]), i));
debug(len, Mp[mp(i, clr)]);
pq.push(mp(len, Mp[mp(i, clr)]));
}
};
auto UPDATE2 = [&](int id, int len) -> void {
debug(2, id);
int v = Mid[id].fs, clr = Mid[id].sc;
for (auto &p : Mv[v][clr]) {
int i = p.fs;
pq.push(mp(len + Mi[v][clr] - p.sc, i));
}
};
dis.resize(C + 1, -1);
pq.push(mp(0LL, 1LL));
while (pq.size()) {
int len = pq.top().fs, id = pq.top().sc;
pq.pop();
if (dis[id] != -1) continue;
dis[id] = len;
debug(id, len);
if (id == to) return dis[id];
if (id <= n) UPDATE1(id, len);
else UPDATE2(id, len);
}
return dis[to];
}
void miku() {
cin >> n >> m;
C = n;
FOR(i, 0, m) {
cin >> a[i] >> b[i] >> c[i] >> p[i];
eid[a[i]].push_back(i);
eid[b[i]].push_back(i);
Mv[a[i]][c[i]].push_back(mp(b[i], p[i]));
Mi[a[i]][c[i]] += p[i];
Mv[b[i]][c[i]].push_back(mp(a[i], p[i]));
Mi[b[i]][c[i]] += p[i];
}
// for (auto &i : eid[1]) {
// debug(i, a[i], b[i]);
// }
FOR(i, 1, n + 1) {
for (auto it = Mv[i].begin(); it != Mv[i].end(); it++) {
// int clr = it -> fs;
// debug(i, clr, Mi[i][clr]);
C++;
Mp[mp(i, it -> fs)] = C;
Mid[C] = mp(i, it -> fs);
}
}
// for (auto i : Mid) debug(i.fs, i.sc.fs, i.sc.sc);
cout << DIJKSTRA(1, n) << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
miku();
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:33:9: note: in expansion of macro 'debug'
33 | debug(id);
| ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:37:13: note: in expansion of macro 'debug'
37 | debug(p[e], Mi[id][clr] - p[e]);
| ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:38:13: note: in expansion of macro 'debug'
38 | debug(len + min(p[e], Mi[id][clr] - p[e]), i);
| ^~~~~
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:40:13: note: in expansion of macro 'debug'
40 | debug(len, Mp[mp(i, clr)]);
| ^~~~~
Main.cpp: In lambda function:
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:45:9: note: in expansion of macro 'debug'
45 | debug(2, id);
| ^~~~~
Main.cpp: In function 'long long int DIJKSTRA(long long int, long long int)':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
Main.cpp:59:9: note: in expansion of macro 'debug'
59 | debug(id, len);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Correct |
6 ms |
29144 KB |
Output is correct |
3 |
Correct |
6 ms |
29192 KB |
Output is correct |
4 |
Correct |
6 ms |
29276 KB |
Output is correct |
5 |
Correct |
6 ms |
29424 KB |
Output is correct |
6 |
Correct |
6 ms |
29276 KB |
Output is correct |
7 |
Correct |
7 ms |
29532 KB |
Output is correct |
8 |
Correct |
7 ms |
29276 KB |
Output is correct |
9 |
Correct |
10 ms |
30552 KB |
Output is correct |
10 |
Correct |
11 ms |
30040 KB |
Output is correct |
11 |
Correct |
9 ms |
29788 KB |
Output is correct |
12 |
Correct |
8 ms |
29880 KB |
Output is correct |
13 |
Correct |
9 ms |
29788 KB |
Output is correct |
14 |
Correct |
8 ms |
29788 KB |
Output is correct |
15 |
Correct |
8 ms |
29532 KB |
Output is correct |
16 |
Correct |
9 ms |
29844 KB |
Output is correct |
17 |
Correct |
8 ms |
29824 KB |
Output is correct |
18 |
Correct |
7 ms |
29528 KB |
Output is correct |
19 |
Correct |
8 ms |
29784 KB |
Output is correct |
20 |
Correct |
8 ms |
29528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
297 ms |
59080 KB |
Output is correct |
2 |
Correct |
112 ms |
44384 KB |
Output is correct |
3 |
Correct |
124 ms |
51412 KB |
Output is correct |
4 |
Correct |
115 ms |
52168 KB |
Output is correct |
5 |
Correct |
1283 ms |
131880 KB |
Output is correct |
6 |
Correct |
985 ms |
109200 KB |
Output is correct |
7 |
Correct |
541 ms |
89500 KB |
Output is correct |
8 |
Correct |
610 ms |
75324 KB |
Output is correct |
9 |
Correct |
676 ms |
75348 KB |
Output is correct |
10 |
Correct |
529 ms |
80320 KB |
Output is correct |
11 |
Correct |
155 ms |
58960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Correct |
6 ms |
29144 KB |
Output is correct |
3 |
Correct |
6 ms |
29192 KB |
Output is correct |
4 |
Correct |
6 ms |
29276 KB |
Output is correct |
5 |
Correct |
6 ms |
29424 KB |
Output is correct |
6 |
Correct |
6 ms |
29276 KB |
Output is correct |
7 |
Correct |
7 ms |
29532 KB |
Output is correct |
8 |
Correct |
7 ms |
29276 KB |
Output is correct |
9 |
Correct |
10 ms |
30552 KB |
Output is correct |
10 |
Correct |
11 ms |
30040 KB |
Output is correct |
11 |
Correct |
9 ms |
29788 KB |
Output is correct |
12 |
Correct |
8 ms |
29880 KB |
Output is correct |
13 |
Correct |
9 ms |
29788 KB |
Output is correct |
14 |
Correct |
8 ms |
29788 KB |
Output is correct |
15 |
Correct |
8 ms |
29532 KB |
Output is correct |
16 |
Correct |
9 ms |
29844 KB |
Output is correct |
17 |
Correct |
8 ms |
29824 KB |
Output is correct |
18 |
Correct |
7 ms |
29528 KB |
Output is correct |
19 |
Correct |
8 ms |
29784 KB |
Output is correct |
20 |
Correct |
8 ms |
29528 KB |
Output is correct |
21 |
Correct |
297 ms |
59080 KB |
Output is correct |
22 |
Correct |
112 ms |
44384 KB |
Output is correct |
23 |
Correct |
124 ms |
51412 KB |
Output is correct |
24 |
Correct |
115 ms |
52168 KB |
Output is correct |
25 |
Correct |
1283 ms |
131880 KB |
Output is correct |
26 |
Correct |
985 ms |
109200 KB |
Output is correct |
27 |
Correct |
541 ms |
89500 KB |
Output is correct |
28 |
Correct |
610 ms |
75324 KB |
Output is correct |
29 |
Correct |
676 ms |
75348 KB |
Output is correct |
30 |
Correct |
529 ms |
80320 KB |
Output is correct |
31 |
Correct |
155 ms |
58960 KB |
Output is correct |
32 |
Correct |
196 ms |
59620 KB |
Output is correct |
33 |
Correct |
176 ms |
53676 KB |
Output is correct |
34 |
Correct |
494 ms |
82632 KB |
Output is correct |
35 |
Correct |
327 ms |
69572 KB |
Output is correct |
36 |
Correct |
523 ms |
77732 KB |
Output is correct |
37 |
Correct |
558 ms |
79268 KB |
Output is correct |
38 |
Correct |
526 ms |
89240 KB |
Output is correct |
39 |
Correct |
257 ms |
56372 KB |
Output is correct |
40 |
Correct |
625 ms |
75444 KB |
Output is correct |
41 |
Correct |
667 ms |
75644 KB |
Output is correct |
42 |
Correct |
879 ms |
99260 KB |
Output is correct |
43 |
Correct |
289 ms |
64704 KB |
Output is correct |
44 |
Correct |
284 ms |
71860 KB |
Output is correct |
45 |
Correct |
545 ms |
70740 KB |
Output is correct |
46 |
Correct |
464 ms |
70740 KB |
Output is correct |
47 |
Correct |
584 ms |
78152 KB |
Output is correct |
48 |
Correct |
1398 ms |
132588 KB |
Output is correct |