#include "Azer.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
namespace
{
int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
int phase; // 1: receive distance, 2: receive node
bool vis[2000] = {};
vector<pii> E[2000];
vector<int> receive;
priority_queue<pii, vector<pii>, greater<pii>> pq;
void send(int message, int bit)
{
for (int i = bit - 1; i >= 0; i--)
SendA((message >> i) & 1);
}
void calcNext()
{
cerr << "calcNextA " << u << ' ' << ld << '\n';
T--;
vis[u] = 1;
d[u] = ld;
for (auto [v, w] : E[u])
if (d[u] + w < d[v])
{
d[v] = d[u] + w;
pq.push(pii(d[v], v));
}
if (T)
{
while (!pq.empty() && vis[pq.top().S])
pq.pop();
if (!pq.empty())
u = pq.top().S, dA = d[u] - ld, dB = 0;
else
u = 0, dA = 511, dB = 0;
send(dA, 9);
phase = 1;
}
}
void check_distance()
{
for (int b = 0; b < 9; b++)
dB = dB * 2 + receive[b];
receive.clear();
if (dB < dA)
phase = 2;
else
{
send(u, 11);
ld += dA;
calcNext();
}
}
void update_distance()
{
u = 0;
ld += dB;
for (int b = 0; b < 11; b++)
u = u * 2 + receive[b];
receive.clear();
calcNext();
}
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C)
{
::N = N;
::T = N;
for (int i = 1; i < N; i++)
d[i] = 1'000'000'000;
for (int i = 0; i < A; i++)
{
E[U[i]].emplace_back(pii(V[i], C[i]));
E[V[i]].emplace_back(pii(U[i], C[i]));
}
calcNext();
}
void ReceiveA(bool x)
{
receive.emplace_back(x);
if (receive.size() == 9 && phase == 1)
check_distance();
if (receive.size() == 11 && phase == 2)
update_distance();
}
std::vector<int> Answer()
{
vector<int> ans(N);
for (int i = 0; i < N; i++)
ans[i] = d[i];
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
namespace
{
int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
int phase; // 1: receive distance, 2: receive node
bool vis[2000] = {};
vector<pii> E[2000];
vector<int> receive;
priority_queue<pii, vector<pii>, greater<pii>> pq;
void send(int message, int bit)
{
for (int i = bit - 1; i >= 0; i--)
SendB((message >> i) & 1);
}
void calcNext()
{
cerr << "calcNextB " << u << ' ' << ld << '\n';
T--;
vis[u] = 1;
d[u] = ld;
for (auto [v, w] : E[u])
if (d[u] + w < d[v])
{
d[v] = d[u] + w;
pq.push(pii(d[v], v));
}
if (T)
{
while (!pq.empty() && vis[pq.top().S])
pq.pop();
if (!pq.empty())
u = pq.top().S, dA = 0, dB = d[u] - ld;
else
u = 0, dA = 0, dB = 511;
send(dB, 9);
phase = 1;
}
}
void check_distance()
{
for (int b = 0; b < 9; b++)
dA = dA * 2 + receive[b];
receive.clear();
if (dA <= dB)
phase = 2;
else
{
send(u, 11);
ld += dB;
calcNext();
}
}
void update_distance()
{
u = 0;
ld += dA;
for (int b = 0; b < 11; b++)
u = u * 2 + receive[b];
receive.clear();
calcNext();
}
}
void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D)
{
::N = N;
::T = N;
for (int i = 1; i < N; i++)
d[i] = 1'000'000'000;
for (int i = 0; i < B; i++)
{
E[S[i]].emplace_back(pii(T[i], D[i]));
E[T[i]].emplace_back(pii(S[i], D[i]));
}
calcNext();
}
void ReceiveB(bool y)
{
receive.emplace_back(y);
if (receive.size() == 9 && phase == 1)
check_distance();
if (receive.size() == 11 && phase == 2)
update_distance();
}
Compilation message
Azer.cpp: In function 'void {anonymous}::calcNext()':
Azer.cpp:30:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto [v, w] : E[u])
| ^
Azer.cpp: At global scope:
Azer.cpp:10:26: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
10 | int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
| ^~~
Baijan.cpp: In function 'void {anonymous}::calcNext()':
Baijan.cpp:30:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto [v, w] : E[u])
| ^
Baijan.cpp: At global scope:
Baijan.cpp:10:26: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
10 | int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
679 ms |
832 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
3 |
Correct |
640 ms |
896 KB |
Output is correct |
4 |
Correct |
782 ms |
10180 KB |
Output is correct |
5 |
Correct |
25 ms |
912 KB |
Output is correct |
6 |
Correct |
610 ms |
2268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
656 KB |
Output is correct |
2 |
Correct |
414 ms |
924 KB |
Output is correct |
3 |
Correct |
646 ms |
924 KB |
Output is correct |
4 |
Correct |
776 ms |
27568 KB |
Output is correct |
5 |
Correct |
820 ms |
24212 KB |
Output is correct |
6 |
Correct |
137 ms |
712 KB |
Output is correct |
7 |
Correct |
686 ms |
24500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
528 ms |
1128 KB |
Output is correct |
2 |
Correct |
0 ms |
656 KB |
Output is correct |
3 |
Correct |
483 ms |
852 KB |
Output is correct |
4 |
Correct |
384 ms |
920 KB |
Output is correct |
5 |
Correct |
550 ms |
1140 KB |
Output is correct |
6 |
Correct |
512 ms |
1136 KB |
Output is correct |
7 |
Correct |
408 ms |
1004 KB |
Output is correct |
8 |
Correct |
474 ms |
1220 KB |
Output is correct |
9 |
Correct |
478 ms |
976 KB |
Output is correct |
10 |
Correct |
573 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
228 ms |
864 KB |
Output is correct |
2 |
Correct |
136 ms |
796 KB |
Output is correct |
3 |
Correct |
361 ms |
13436 KB |
Output is correct |
4 |
Correct |
258 ms |
792 KB |
Output is correct |
5 |
Correct |
304 ms |
10048 KB |
Output is correct |
6 |
Correct |
196 ms |
924 KB |
Output is correct |
7 |
Correct |
281 ms |
828 KB |
Output is correct |
8 |
Correct |
183 ms |
836 KB |
Output is correct |
9 |
Correct |
331 ms |
18200 KB |
Output is correct |
10 |
Correct |
361 ms |
18448 KB |
Output is correct |
11 |
Correct |
404 ms |
35748 KB |
Output is correct |
12 |
Correct |
437 ms |
30600 KB |
Output is correct |
13 |
Correct |
276 ms |
1128 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
228 ms |
864 KB |
Output is correct |
2 |
Correct |
136 ms |
796 KB |
Output is correct |
3 |
Correct |
361 ms |
13436 KB |
Output is correct |
4 |
Correct |
258 ms |
792 KB |
Output is correct |
5 |
Correct |
304 ms |
10048 KB |
Output is correct |
6 |
Correct |
196 ms |
924 KB |
Output is correct |
7 |
Correct |
281 ms |
828 KB |
Output is correct |
8 |
Correct |
183 ms |
836 KB |
Output is correct |
9 |
Correct |
331 ms |
18200 KB |
Output is correct |
10 |
Correct |
361 ms |
18448 KB |
Output is correct |
11 |
Correct |
404 ms |
35748 KB |
Output is correct |
12 |
Correct |
437 ms |
30600 KB |
Output is correct |
13 |
Correct |
276 ms |
1128 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
360 ms |
1136 KB |
Output is correct |
16 |
Correct |
281 ms |
764 KB |
Output is correct |
17 |
Correct |
264 ms |
768 KB |
Output is correct |
18 |
Correct |
397 ms |
10140 KB |
Output is correct |
19 |
Correct |
323 ms |
816 KB |
Output is correct |
20 |
Correct |
355 ms |
10380 KB |
Output is correct |
21 |
Correct |
280 ms |
864 KB |
Output is correct |
22 |
Correct |
306 ms |
864 KB |
Output is correct |
23 |
Correct |
399 ms |
22164 KB |
Output is correct |
24 |
Correct |
318 ms |
22160 KB |
Output is correct |
25 |
Correct |
625 ms |
43516 KB |
Output is correct |
26 |
Correct |
445 ms |
36368 KB |
Output is correct |
27 |
Correct |
260 ms |
1020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
228 ms |
864 KB |
Output is correct |
2 |
Correct |
136 ms |
796 KB |
Output is correct |
3 |
Correct |
361 ms |
13436 KB |
Output is correct |
4 |
Correct |
258 ms |
792 KB |
Output is correct |
5 |
Correct |
304 ms |
10048 KB |
Output is correct |
6 |
Correct |
196 ms |
924 KB |
Output is correct |
7 |
Correct |
281 ms |
828 KB |
Output is correct |
8 |
Correct |
183 ms |
836 KB |
Output is correct |
9 |
Correct |
331 ms |
18200 KB |
Output is correct |
10 |
Correct |
361 ms |
18448 KB |
Output is correct |
11 |
Correct |
404 ms |
35748 KB |
Output is correct |
12 |
Correct |
437 ms |
30600 KB |
Output is correct |
13 |
Correct |
276 ms |
1128 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
360 ms |
1136 KB |
Output is correct |
16 |
Correct |
281 ms |
764 KB |
Output is correct |
17 |
Correct |
264 ms |
768 KB |
Output is correct |
18 |
Correct |
397 ms |
10140 KB |
Output is correct |
19 |
Correct |
323 ms |
816 KB |
Output is correct |
20 |
Correct |
355 ms |
10380 KB |
Output is correct |
21 |
Correct |
280 ms |
864 KB |
Output is correct |
22 |
Correct |
306 ms |
864 KB |
Output is correct |
23 |
Correct |
399 ms |
22164 KB |
Output is correct |
24 |
Correct |
318 ms |
22160 KB |
Output is correct |
25 |
Correct |
625 ms |
43516 KB |
Output is correct |
26 |
Correct |
445 ms |
36368 KB |
Output is correct |
27 |
Correct |
260 ms |
1020 KB |
Output is correct |
28 |
Correct |
376 ms |
924 KB |
Output is correct |
29 |
Correct |
443 ms |
1036 KB |
Output is correct |
30 |
Correct |
524 ms |
24120 KB |
Output is correct |
31 |
Correct |
390 ms |
896 KB |
Output is correct |
32 |
Correct |
308 ms |
21072 KB |
Output is correct |
33 |
Correct |
414 ms |
1096 KB |
Output is correct |
34 |
Correct |
433 ms |
1276 KB |
Output is correct |
35 |
Correct |
415 ms |
916 KB |
Output is correct |
36 |
Correct |
514 ms |
24860 KB |
Output is correct |
37 |
Correct |
490 ms |
24732 KB |
Output is correct |
38 |
Correct |
539 ms |
48852 KB |
Output is correct |
39 |
Correct |
556 ms |
44296 KB |
Output is correct |
40 |
Correct |
363 ms |
1076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
679 ms |
832 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
3 |
Correct |
640 ms |
896 KB |
Output is correct |
4 |
Correct |
782 ms |
10180 KB |
Output is correct |
5 |
Correct |
25 ms |
912 KB |
Output is correct |
6 |
Correct |
610 ms |
2268 KB |
Output is correct |
7 |
Correct |
1 ms |
656 KB |
Output is correct |
8 |
Correct |
414 ms |
924 KB |
Output is correct |
9 |
Correct |
646 ms |
924 KB |
Output is correct |
10 |
Correct |
776 ms |
27568 KB |
Output is correct |
11 |
Correct |
820 ms |
24212 KB |
Output is correct |
12 |
Correct |
137 ms |
712 KB |
Output is correct |
13 |
Correct |
686 ms |
24500 KB |
Output is correct |
14 |
Correct |
528 ms |
1128 KB |
Output is correct |
15 |
Correct |
0 ms |
656 KB |
Output is correct |
16 |
Correct |
483 ms |
852 KB |
Output is correct |
17 |
Correct |
384 ms |
920 KB |
Output is correct |
18 |
Correct |
550 ms |
1140 KB |
Output is correct |
19 |
Correct |
512 ms |
1136 KB |
Output is correct |
20 |
Correct |
408 ms |
1004 KB |
Output is correct |
21 |
Correct |
474 ms |
1220 KB |
Output is correct |
22 |
Correct |
478 ms |
976 KB |
Output is correct |
23 |
Correct |
573 ms |
1228 KB |
Output is correct |
24 |
Correct |
228 ms |
864 KB |
Output is correct |
25 |
Correct |
136 ms |
796 KB |
Output is correct |
26 |
Correct |
361 ms |
13436 KB |
Output is correct |
27 |
Correct |
258 ms |
792 KB |
Output is correct |
28 |
Correct |
304 ms |
10048 KB |
Output is correct |
29 |
Correct |
196 ms |
924 KB |
Output is correct |
30 |
Correct |
281 ms |
828 KB |
Output is correct |
31 |
Correct |
183 ms |
836 KB |
Output is correct |
32 |
Correct |
331 ms |
18200 KB |
Output is correct |
33 |
Correct |
361 ms |
18448 KB |
Output is correct |
34 |
Correct |
404 ms |
35748 KB |
Output is correct |
35 |
Correct |
437 ms |
30600 KB |
Output is correct |
36 |
Correct |
276 ms |
1128 KB |
Output is correct |
37 |
Correct |
0 ms |
656 KB |
Output is correct |
38 |
Correct |
360 ms |
1136 KB |
Output is correct |
39 |
Correct |
281 ms |
764 KB |
Output is correct |
40 |
Correct |
264 ms |
768 KB |
Output is correct |
41 |
Correct |
397 ms |
10140 KB |
Output is correct |
42 |
Correct |
323 ms |
816 KB |
Output is correct |
43 |
Correct |
355 ms |
10380 KB |
Output is correct |
44 |
Correct |
280 ms |
864 KB |
Output is correct |
45 |
Correct |
306 ms |
864 KB |
Output is correct |
46 |
Correct |
399 ms |
22164 KB |
Output is correct |
47 |
Correct |
318 ms |
22160 KB |
Output is correct |
48 |
Correct |
625 ms |
43516 KB |
Output is correct |
49 |
Correct |
445 ms |
36368 KB |
Output is correct |
50 |
Correct |
260 ms |
1020 KB |
Output is correct |
51 |
Correct |
376 ms |
924 KB |
Output is correct |
52 |
Correct |
443 ms |
1036 KB |
Output is correct |
53 |
Correct |
524 ms |
24120 KB |
Output is correct |
54 |
Correct |
390 ms |
896 KB |
Output is correct |
55 |
Correct |
308 ms |
21072 KB |
Output is correct |
56 |
Correct |
414 ms |
1096 KB |
Output is correct |
57 |
Correct |
433 ms |
1276 KB |
Output is correct |
58 |
Correct |
415 ms |
916 KB |
Output is correct |
59 |
Correct |
514 ms |
24860 KB |
Output is correct |
60 |
Correct |
490 ms |
24732 KB |
Output is correct |
61 |
Correct |
539 ms |
48852 KB |
Output is correct |
62 |
Correct |
556 ms |
44296 KB |
Output is correct |
63 |
Correct |
363 ms |
1076 KB |
Output is correct |
64 |
Correct |
524 ms |
1308 KB |
Output is correct |
65 |
Correct |
574 ms |
26500 KB |
Output is correct |
66 |
Correct |
663 ms |
23340 KB |
Output is correct |
67 |
Correct |
508 ms |
1264 KB |
Output is correct |
68 |
Correct |
577 ms |
1412 KB |
Output is correct |
69 |
Correct |
912 ms |
47636 KB |
Output is correct |
70 |
Correct |
845 ms |
39444 KB |
Output is correct |
71 |
Correct |
673 ms |
5024 KB |
Output is correct |
72 |
Correct |
570 ms |
1248 KB |
Output is correct |