#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace a {
int N;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int max_until_now = 0;
bool receive_length = 0;
int cnt_length;
int length, length_a;
int pos, cnt_pos;
int a;
void send_nude(int du, int u) {
// cerr << du << ' ' << u << '\n';
length_a = du - max_until_now;
a = u;
// cerr << "now sending length " << length_a << " from a to b!\n";
for (int i = 0; i < 9; i++) SendA(length_a >> i & 1);
receive_length = 1;
cnt_length = length = 0;
}
void try_next() {
while (pq.size()) {
auto [du, u] = pq.top();
// cerr << "pq : " << du << ' ' << u << '\n';
if (done[u] == 0) {
send_nude(-du, u);
return;
}
pq.pop();
// cerr << d[u] << '\n';
if (-du != d[u]) continue;
max_until_now = -du;
for (auto [v, w] : adj[u]) {
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.emplace(-d[v], v);
}
}
}
for (int i = 0; i < N; i++) {
if (done[i] == 0) {
send_nude(max_until_now + 511, 0);
return;
}
}
}
} // namespace a
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
a::N = N;
a::adj.resize(N);
a::d.assign(N, 1e9);
a::done.assign(N, 0);
for (int i = 0; i < A; i++) a::adj[U[i]].emplace_back(V[i], C[i]);
for (int i = 0; i < A; i++) a::adj[V[i]].emplace_back(U[i], C[i]);
a::pq.emplace(0, 0);
a::d[0] = 0;
a::done[0] = 1;
a::try_next();
}
void ReceiveA(bool x) {
if (a::receive_length) {
a::length |= x << a::cnt_length;
a::cnt_length++;
if (a::cnt_length == 9) {
// cerr << "now receiving length " << a::length << " from b to a\n";
if (a::length < a::length_a) {
a::length += a::max_until_now;
a::pos = a::cnt_pos = 0;
a::receive_length = 0;
} else {
// cerr << "now sending pos " << a::a << " from a to b!\n";
for (int i = 0; i < 11; i++) SendA(a::a >> i & 1);
a::done[a::a] = 1;
a::try_next();
}
}
} else {
a::pos |= x << a::cnt_pos;
a::cnt_pos++;
if (a::cnt_pos == 11) {
// cerr << a::max_until_now << '\n';
// cerr << "now receiving pos " << a::pos << " from b to a!\n";
a::done[a::pos] = 1;
a::d[a::pos] = a::length;
a::pq.emplace(-a::length, a::pos);
a::try_next();
}
}
}
std::vector<int> Answer() {
return a::d;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace b {
int N;
int x = 0;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int length, cnt_length;
bool receive_length;
int length_b;
int max_until_now;
int pos, cnt_pos;
void send_nude(int du, int u) {
// cerr << "send_nude on b: " << du << ' ' << u << '\n';
int length_b = du - max_until_now;
// cerr << "now sending " << length_b << " from b to a!\n";
for (int i = 0; i < 9; i++) SendB(length_b >> i & 1);
if (length_b < length) {
for (int i = 0; i < 11; i++) SendB(u >> i & 1);
done[u] = 1;
length = cnt_length = 0;
receive_length = 1;
} else {
receive_length = 0;
pos = 0, cnt_pos = 0;
}
}
} // namespace b
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
b::N = N;
b::adj.resize(N);
b::d.assign(N, 1e9);
b::done.assign(N, 0);
for (int i = 0; i < B; i++) b::adj[S[i]].emplace_back(T[i], D[i]);
for (int i = 0; i < B; i++) b::adj[T[i]].emplace_back(S[i], D[i]);
b::pq.emplace(0, 0);
b::d[0] = 0;
b::done[0] = 1;
b::max_until_now = 0;
b::receive_length = 1;
b::length = b::cnt_length = 0;
}
void ReceiveB(bool y) {
if (b::receive_length) {
b::length |= y << b::cnt_length;
b::cnt_length++;
if (b::cnt_length == 9) {
bool ok = 1;
for (int i = 0; i < b::N; i++) ok &= b::done[i];
// cerr << "now receiving length " << b::length << " from a to b\n";
while (b::pq.size()) {
auto [du, u] = b::pq.top();
if (b::done[u] == 0) {
b::send_nude(-du, u);
ok = 1;
break;
}
b::pq.pop();
if (-du != b::d[u]) continue;
b::max_until_now = -du;
for (auto&& [v, w] : b::adj[u]) {
if (b::d[v] > b::d[u] + w) {
b::d[v] = b::d[u] + w;
b::pq.emplace(-b::d[v], v);
}
}
}
if (!ok) b::send_nude(b::max_until_now + 511, 0);
}
} else {
b::pos |= y << b::cnt_pos;
b::cnt_pos++;
if (b::cnt_pos == 11) {
// cerr << "now receiving pos " << b::pos << " from a to b!\n";
b::d[b::pos] = b::length + b::max_until_now;
b::max_until_now = b::d[b::pos];
b::pq.emplace(-b::d[b::pos], b::pos);
b::done[b::pos] = 1;
b::receive_length = 1;
b::cnt_length = b::length = 0;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
369 ms |
1056 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
343 ms |
1056 KB |
Output is correct |
4 |
Correct |
454 ms |
10436 KB |
Output is correct |
5 |
Correct |
13 ms |
920 KB |
Output is correct |
6 |
Correct |
301 ms |
2336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
664 KB |
Output is correct |
2 |
Correct |
280 ms |
884 KB |
Output is correct |
3 |
Correct |
322 ms |
936 KB |
Output is correct |
4 |
Correct |
459 ms |
27668 KB |
Output is correct |
5 |
Correct |
403 ms |
24364 KB |
Output is correct |
6 |
Correct |
56 ms |
748 KB |
Output is correct |
7 |
Correct |
434 ms |
24500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
868 KB |
Output is correct |
2 |
Correct |
1 ms |
664 KB |
Output is correct |
3 |
Correct |
311 ms |
1056 KB |
Output is correct |
4 |
Correct |
271 ms |
896 KB |
Output is correct |
5 |
Correct |
321 ms |
880 KB |
Output is correct |
6 |
Correct |
287 ms |
872 KB |
Output is correct |
7 |
Correct |
267 ms |
880 KB |
Output is correct |
8 |
Correct |
311 ms |
800 KB |
Output is correct |
9 |
Correct |
283 ms |
1056 KB |
Output is correct |
10 |
Correct |
267 ms |
1076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
800 KB |
Output is correct |
2 |
Correct |
106 ms |
764 KB |
Output is correct |
3 |
Correct |
191 ms |
13348 KB |
Output is correct |
4 |
Correct |
109 ms |
664 KB |
Output is correct |
5 |
Correct |
218 ms |
9972 KB |
Output is correct |
6 |
Correct |
145 ms |
1056 KB |
Output is correct |
7 |
Correct |
119 ms |
832 KB |
Output is correct |
8 |
Correct |
119 ms |
836 KB |
Output is correct |
9 |
Correct |
224 ms |
18304 KB |
Output is correct |
10 |
Correct |
232 ms |
18144 KB |
Output is correct |
11 |
Correct |
309 ms |
35776 KB |
Output is correct |
12 |
Correct |
282 ms |
30696 KB |
Output is correct |
13 |
Correct |
112 ms |
664 KB |
Output is correct |
14 |
Correct |
0 ms |
672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
800 KB |
Output is correct |
2 |
Correct |
106 ms |
764 KB |
Output is correct |
3 |
Correct |
191 ms |
13348 KB |
Output is correct |
4 |
Correct |
109 ms |
664 KB |
Output is correct |
5 |
Correct |
218 ms |
9972 KB |
Output is correct |
6 |
Correct |
145 ms |
1056 KB |
Output is correct |
7 |
Correct |
119 ms |
832 KB |
Output is correct |
8 |
Correct |
119 ms |
836 KB |
Output is correct |
9 |
Correct |
224 ms |
18304 KB |
Output is correct |
10 |
Correct |
232 ms |
18144 KB |
Output is correct |
11 |
Correct |
309 ms |
35776 KB |
Output is correct |
12 |
Correct |
282 ms |
30696 KB |
Output is correct |
13 |
Correct |
112 ms |
664 KB |
Output is correct |
14 |
Correct |
0 ms |
672 KB |
Output is correct |
15 |
Correct |
158 ms |
664 KB |
Output is correct |
16 |
Correct |
176 ms |
664 KB |
Output is correct |
17 |
Correct |
186 ms |
664 KB |
Output is correct |
18 |
Correct |
215 ms |
10508 KB |
Output is correct |
19 |
Correct |
221 ms |
664 KB |
Output is correct |
20 |
Correct |
194 ms |
10680 KB |
Output is correct |
21 |
Correct |
164 ms |
664 KB |
Output is correct |
22 |
Correct |
147 ms |
664 KB |
Output is correct |
23 |
Correct |
274 ms |
22484 KB |
Output is correct |
24 |
Correct |
298 ms |
22344 KB |
Output is correct |
25 |
Correct |
374 ms |
43816 KB |
Output is correct |
26 |
Correct |
301 ms |
36660 KB |
Output is correct |
27 |
Correct |
140 ms |
872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
800 KB |
Output is correct |
2 |
Correct |
106 ms |
764 KB |
Output is correct |
3 |
Correct |
191 ms |
13348 KB |
Output is correct |
4 |
Correct |
109 ms |
664 KB |
Output is correct |
5 |
Correct |
218 ms |
9972 KB |
Output is correct |
6 |
Correct |
145 ms |
1056 KB |
Output is correct |
7 |
Correct |
119 ms |
832 KB |
Output is correct |
8 |
Correct |
119 ms |
836 KB |
Output is correct |
9 |
Correct |
224 ms |
18304 KB |
Output is correct |
10 |
Correct |
232 ms |
18144 KB |
Output is correct |
11 |
Correct |
309 ms |
35776 KB |
Output is correct |
12 |
Correct |
282 ms |
30696 KB |
Output is correct |
13 |
Correct |
112 ms |
664 KB |
Output is correct |
14 |
Correct |
0 ms |
672 KB |
Output is correct |
15 |
Correct |
158 ms |
664 KB |
Output is correct |
16 |
Correct |
176 ms |
664 KB |
Output is correct |
17 |
Correct |
186 ms |
664 KB |
Output is correct |
18 |
Correct |
215 ms |
10508 KB |
Output is correct |
19 |
Correct |
221 ms |
664 KB |
Output is correct |
20 |
Correct |
194 ms |
10680 KB |
Output is correct |
21 |
Correct |
164 ms |
664 KB |
Output is correct |
22 |
Correct |
147 ms |
664 KB |
Output is correct |
23 |
Correct |
274 ms |
22484 KB |
Output is correct |
24 |
Correct |
298 ms |
22344 KB |
Output is correct |
25 |
Correct |
374 ms |
43816 KB |
Output is correct |
26 |
Correct |
301 ms |
36660 KB |
Output is correct |
27 |
Correct |
140 ms |
872 KB |
Output is correct |
28 |
Correct |
200 ms |
664 KB |
Output is correct |
29 |
Correct |
176 ms |
844 KB |
Output is correct |
30 |
Correct |
318 ms |
24124 KB |
Output is correct |
31 |
Correct |
222 ms |
780 KB |
Output is correct |
32 |
Correct |
287 ms |
21144 KB |
Output is correct |
33 |
Correct |
174 ms |
856 KB |
Output is correct |
34 |
Correct |
233 ms |
884 KB |
Output is correct |
35 |
Correct |
198 ms |
888 KB |
Output is correct |
36 |
Correct |
378 ms |
24864 KB |
Output is correct |
37 |
Correct |
338 ms |
25348 KB |
Output is correct |
38 |
Correct |
449 ms |
49080 KB |
Output is correct |
39 |
Correct |
437 ms |
44200 KB |
Output is correct |
40 |
Correct |
199 ms |
1176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
369 ms |
1056 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
343 ms |
1056 KB |
Output is correct |
4 |
Correct |
454 ms |
10436 KB |
Output is correct |
5 |
Correct |
13 ms |
920 KB |
Output is correct |
6 |
Correct |
301 ms |
2336 KB |
Output is correct |
7 |
Correct |
0 ms |
664 KB |
Output is correct |
8 |
Correct |
280 ms |
884 KB |
Output is correct |
9 |
Correct |
322 ms |
936 KB |
Output is correct |
10 |
Correct |
459 ms |
27668 KB |
Output is correct |
11 |
Correct |
403 ms |
24364 KB |
Output is correct |
12 |
Correct |
56 ms |
748 KB |
Output is correct |
13 |
Correct |
434 ms |
24500 KB |
Output is correct |
14 |
Correct |
325 ms |
868 KB |
Output is correct |
15 |
Correct |
1 ms |
664 KB |
Output is correct |
16 |
Correct |
311 ms |
1056 KB |
Output is correct |
17 |
Correct |
271 ms |
896 KB |
Output is correct |
18 |
Correct |
321 ms |
880 KB |
Output is correct |
19 |
Correct |
287 ms |
872 KB |
Output is correct |
20 |
Correct |
267 ms |
880 KB |
Output is correct |
21 |
Correct |
311 ms |
800 KB |
Output is correct |
22 |
Correct |
283 ms |
1056 KB |
Output is correct |
23 |
Correct |
267 ms |
1076 KB |
Output is correct |
24 |
Correct |
159 ms |
800 KB |
Output is correct |
25 |
Correct |
106 ms |
764 KB |
Output is correct |
26 |
Correct |
191 ms |
13348 KB |
Output is correct |
27 |
Correct |
109 ms |
664 KB |
Output is correct |
28 |
Correct |
218 ms |
9972 KB |
Output is correct |
29 |
Correct |
145 ms |
1056 KB |
Output is correct |
30 |
Correct |
119 ms |
832 KB |
Output is correct |
31 |
Correct |
119 ms |
836 KB |
Output is correct |
32 |
Correct |
224 ms |
18304 KB |
Output is correct |
33 |
Correct |
232 ms |
18144 KB |
Output is correct |
34 |
Correct |
309 ms |
35776 KB |
Output is correct |
35 |
Correct |
282 ms |
30696 KB |
Output is correct |
36 |
Correct |
112 ms |
664 KB |
Output is correct |
37 |
Correct |
0 ms |
672 KB |
Output is correct |
38 |
Correct |
158 ms |
664 KB |
Output is correct |
39 |
Correct |
176 ms |
664 KB |
Output is correct |
40 |
Correct |
186 ms |
664 KB |
Output is correct |
41 |
Correct |
215 ms |
10508 KB |
Output is correct |
42 |
Correct |
221 ms |
664 KB |
Output is correct |
43 |
Correct |
194 ms |
10680 KB |
Output is correct |
44 |
Correct |
164 ms |
664 KB |
Output is correct |
45 |
Correct |
147 ms |
664 KB |
Output is correct |
46 |
Correct |
274 ms |
22484 KB |
Output is correct |
47 |
Correct |
298 ms |
22344 KB |
Output is correct |
48 |
Correct |
374 ms |
43816 KB |
Output is correct |
49 |
Correct |
301 ms |
36660 KB |
Output is correct |
50 |
Correct |
140 ms |
872 KB |
Output is correct |
51 |
Correct |
200 ms |
664 KB |
Output is correct |
52 |
Correct |
176 ms |
844 KB |
Output is correct |
53 |
Correct |
318 ms |
24124 KB |
Output is correct |
54 |
Correct |
222 ms |
780 KB |
Output is correct |
55 |
Correct |
287 ms |
21144 KB |
Output is correct |
56 |
Correct |
174 ms |
856 KB |
Output is correct |
57 |
Correct |
233 ms |
884 KB |
Output is correct |
58 |
Correct |
198 ms |
888 KB |
Output is correct |
59 |
Correct |
378 ms |
24864 KB |
Output is correct |
60 |
Correct |
338 ms |
25348 KB |
Output is correct |
61 |
Correct |
449 ms |
49080 KB |
Output is correct |
62 |
Correct |
437 ms |
44200 KB |
Output is correct |
63 |
Correct |
199 ms |
1176 KB |
Output is correct |
64 |
Correct |
271 ms |
1228 KB |
Output is correct |
65 |
Correct |
475 ms |
26680 KB |
Output is correct |
66 |
Correct |
459 ms |
23548 KB |
Output is correct |
67 |
Correct |
307 ms |
1204 KB |
Output is correct |
68 |
Correct |
304 ms |
1204 KB |
Output is correct |
69 |
Correct |
679 ms |
48156 KB |
Output is correct |
70 |
Correct |
552 ms |
39564 KB |
Output is correct |
71 |
Correct |
337 ms |
5256 KB |
Output is correct |
72 |
Correct |
323 ms |
1176 KB |
Output is correct |