#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
namespace {
ll N, A;
vector<ll> dis, chk;
vector<ll> U, V, C;
ll cnt = 0;
ll c, v;
ll pmv;
ll pmn;
ll pv;
ll res;
ll mode = 0;
ll mv;
ll val;
pair<ll, ll> ppv = { 0, -1000 };
priority_queue<pair<ll, ll>> pq;
vector<vector<pair<ll, ll>>> adj;
void send(ll, ll);
void func();
void send(ll x, ll a) {
ll i;
for (i = a - 1; i >= 0; i--) SendA(x & (1 << i));
}
void func() {
ll i;
ll asdfsdf = 1;
for (i = 1; i < N; i++) if (!chk[i]) asdfsdf = 0;
if (asdfsdf) return;
ll mn = 101010;
mv = -1;
pair<ll, ll> t;
while (pq.size()) {
t = pq.top();
pq.pop();
if (t.second == -1000) continue;
if (chk[t.second]) continue;
mv = t.second;
break;
}
ppv = t;
if (mv == -1) val = 511;
else val = -t.first - pv;
send(val, 9);
}
} // namespace
void ReceiveA(bool x) {
res *= 2;
if (x) res++;
cnt++;
if (mode == 0) {
if (cnt == 9) {
cnt = 0;
if (val <= res) {
send(mv, 11);
dis[mv] = val + pv;
pv = dis[mv];
chk[mv] = 1;
res = 0;
for (auto x : adj[mv]) {
if (chk[x.first]) continue;
pq.emplace(-(x.second + dis[mv]), x.first);
}
func();
}
else mode = 1, val = res, res = 0, pq.push(ppv), ppv = { 0, -1000 };
}
}
else {
if (cnt == 11) {
dis[res] = val + pv;
pv = dis[res];
chk[res] = 1;
cnt = 0;
mode = 0;
for (auto x : adj[res]) {
if (chk[x.first]) continue;
pq.emplace(-(x.second + dis[res]), x.first);
}
res = 0;
func();
}
}
}
std::vector<int> Answer() {
return dis;
}
void InitA(int _N, int _A, vector<ll> _U, vector<ll> _V, vector<ll> _C) {
tie(N, A, U, V, C) = make_tuple(_N, _A, _U, _V, _C);
dis.resize(N);
chk.resize(N);
ll i;
for (i = 1; i < N; i++) dis[i] = 1010101010;
chk[0] = 1;
mode = 0;
res = 0;
adj.resize(N);
for (i = 0; i < A; i++) adj[U[i]].emplace_back(V[i], C[i]), adj[V[i]].emplace_back(U[i], C[i]);
for (i = 0; i < adj[0].size(); i++) pq.emplace(-adj[0][i].second, adj[0][i].first);
func();
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
namespace {
ll N, B;
ll cnt = 0;
vector<ll> S, T, D;
ll res = 0;
ll pv = 0;
ll mode;
vector<ll> chk;
vector<ll> dis;
ll val;
ll mv;
pair<ll, ll> ppv = { 0, -1000 };
priority_queue<pair<ll, ll>> pq;
vector<vector<pair<ll, ll>>> adj;
void send(ll x, ll a) {
ll i;
for (i = a - 1; i >= 0; i--) SendB(x & (1 << i));
}
void func() {
ll i;
ll mn = 511;
mv = -1;
pair<ll, ll> t;
while (pq.size()) {
t = pq.top();
pq.pop();
if (t.second == -1000) continue;
if (chk[t.second]) continue;
mv = t.second;
break;
}
ppv = t;
if (mv == -1) val = 511;
else val = min(511, -t.first - pv);
}
} // namespace
void InitB(int _N, int _B, vector<int> _S, vector<int> _T, vector<int> _D) {
tie(N, B, S, T, D) = make_tuple(_N, _B, _S, _T, _D);
ll i;
dis.resize(N);
chk.resize(N);
for (i = 1; i < N; i++) dis[i] = 1010101010;
chk[0] = 1;
mode = 0;
res = 0;
adj.resize(N);
for (i = 0; i < B; i++) adj[S[i]].emplace_back(T[i], D[i]), adj[T[i]].emplace_back(S[i], D[i]);
for (i = 0; i < adj[0].size(); i++) pq.emplace(-adj[0][i].second, adj[0][i].first);
}
void ReceiveB(bool y) {
res *= 2;
if (y) res++;
cnt++;
if (!mode) {
if (cnt == 9) {
func();
send(val, 9);
cnt = 0;
if (val < res) {
send(mv, 11);
dis[mv] = pv + val;
pv = dis[mv];
chk[mv] = 1;
res = 0;
for (auto x : adj[mv]) {
if (chk[x.first]) continue;
pq.emplace(-(x.second + dis[mv]), x.first);
}
}
else mode = 1, val = res, res = 0, pq.push(ppv), ppv = { 0, -1000 };
}
}
else {
if (cnt == 11) {
cnt = 0;
dis[res] = val + pv;
pv = dis[res];
chk[res] = 1;
mode = 0;
for (auto x : adj[res]) {
if (chk[x.first]) continue;
pq.emplace(-(x.second + dis[res]), x.first);
}
res = 0;
}
}
}
Compilation message
Azer.cpp: In function 'void {anonymous}::func()':
Azer.cpp:35:6: warning: unused variable 'mn' [-Wunused-variable]
35 | ll mn = 101010;
| ^~
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:109:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (i = 0; i < adj[0].size(); i++) pq.emplace(-adj[0][i].second, adj[0][i].first);
| ~~^~~~~~~~~~~~~~~
Azer.cpp: At global scope:
Azer.cpp:13:5: warning: '{anonymous}::pmn' defined but not used [-Wunused-variable]
13 | ll pmn;
| ^~~
Azer.cpp:12:5: warning: '{anonymous}::pmv' defined but not used [-Wunused-variable]
12 | ll pmv;
| ^~~
Azer.cpp:11:8: warning: '{anonymous}::v' defined but not used [-Wunused-variable]
11 | ll c, v;
| ^
Azer.cpp:11:5: warning: '{anonymous}::c' defined but not used [-Wunused-variable]
11 | ll c, v;
| ^
Baijan.cpp: In function 'void {anonymous}::func()':
Baijan.cpp:27:6: warning: unused variable 'i' [-Wunused-variable]
27 | ll i;
| ^
Baijan.cpp:28:6: warning: unused variable 'mn' [-Wunused-variable]
28 | ll mn = 511;
| ^~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:56:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (i = 0; i < adj[0].size(); i++) pq.emplace(-adj[0][i].second, adj[0][i].first);
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
788 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
588 ms |
780 KB |
Output is correct |
4 |
Correct |
724 ms |
12624 KB |
Output is correct |
5 |
Correct |
39 ms |
920 KB |
Output is correct |
6 |
Correct |
567 ms |
2896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
466 ms |
744 KB |
Output is correct |
3 |
Correct |
595 ms |
824 KB |
Output is correct |
4 |
Correct |
774 ms |
33280 KB |
Output is correct |
5 |
Correct |
798 ms |
30484 KB |
Output is correct |
6 |
Correct |
114 ms |
636 KB |
Output is correct |
7 |
Correct |
819 ms |
30468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
608 ms |
744 KB |
Output is correct |
2 |
Correct |
0 ms |
388 KB |
Output is correct |
3 |
Correct |
576 ms |
784 KB |
Output is correct |
4 |
Correct |
638 ms |
752 KB |
Output is correct |
5 |
Correct |
622 ms |
748 KB |
Output is correct |
6 |
Correct |
621 ms |
736 KB |
Output is correct |
7 |
Correct |
681 ms |
752 KB |
Output is correct |
8 |
Correct |
545 ms |
788 KB |
Output is correct |
9 |
Correct |
538 ms |
788 KB |
Output is correct |
10 |
Correct |
526 ms |
776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
656 KB |
Output is correct |
2 |
Correct |
301 ms |
616 KB |
Output is correct |
3 |
Correct |
413 ms |
16028 KB |
Output is correct |
4 |
Correct |
310 ms |
608 KB |
Output is correct |
5 |
Correct |
389 ms |
12368 KB |
Output is correct |
6 |
Correct |
249 ms |
640 KB |
Output is correct |
7 |
Correct |
246 ms |
640 KB |
Output is correct |
8 |
Correct |
283 ms |
696 KB |
Output is correct |
9 |
Correct |
405 ms |
24144 KB |
Output is correct |
10 |
Correct |
378 ms |
24248 KB |
Output is correct |
11 |
Correct |
575 ms |
47740 KB |
Output is correct |
12 |
Correct |
521 ms |
43208 KB |
Output is correct |
13 |
Correct |
273 ms |
644 KB |
Output is correct |
14 |
Correct |
1 ms |
388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
656 KB |
Output is correct |
2 |
Correct |
301 ms |
616 KB |
Output is correct |
3 |
Correct |
413 ms |
16028 KB |
Output is correct |
4 |
Correct |
310 ms |
608 KB |
Output is correct |
5 |
Correct |
389 ms |
12368 KB |
Output is correct |
6 |
Correct |
249 ms |
640 KB |
Output is correct |
7 |
Correct |
246 ms |
640 KB |
Output is correct |
8 |
Correct |
283 ms |
696 KB |
Output is correct |
9 |
Correct |
405 ms |
24144 KB |
Output is correct |
10 |
Correct |
378 ms |
24248 KB |
Output is correct |
11 |
Correct |
575 ms |
47740 KB |
Output is correct |
12 |
Correct |
521 ms |
43208 KB |
Output is correct |
13 |
Correct |
273 ms |
644 KB |
Output is correct |
14 |
Correct |
1 ms |
388 KB |
Output is correct |
15 |
Correct |
256 ms |
640 KB |
Output is correct |
16 |
Correct |
273 ms |
572 KB |
Output is correct |
17 |
Correct |
295 ms |
516 KB |
Output is correct |
18 |
Correct |
461 ms |
12324 KB |
Output is correct |
19 |
Correct |
340 ms |
640 KB |
Output is correct |
20 |
Correct |
479 ms |
12864 KB |
Output is correct |
21 |
Correct |
307 ms |
712 KB |
Output is correct |
22 |
Correct |
337 ms |
760 KB |
Output is correct |
23 |
Correct |
402 ms |
28236 KB |
Output is correct |
24 |
Correct |
540 ms |
28344 KB |
Output is correct |
25 |
Correct |
710 ms |
55764 KB |
Output is correct |
26 |
Correct |
548 ms |
48820 KB |
Output is correct |
27 |
Correct |
314 ms |
864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
656 KB |
Output is correct |
2 |
Correct |
301 ms |
616 KB |
Output is correct |
3 |
Correct |
413 ms |
16028 KB |
Output is correct |
4 |
Correct |
310 ms |
608 KB |
Output is correct |
5 |
Correct |
389 ms |
12368 KB |
Output is correct |
6 |
Correct |
249 ms |
640 KB |
Output is correct |
7 |
Correct |
246 ms |
640 KB |
Output is correct |
8 |
Correct |
283 ms |
696 KB |
Output is correct |
9 |
Correct |
405 ms |
24144 KB |
Output is correct |
10 |
Correct |
378 ms |
24248 KB |
Output is correct |
11 |
Correct |
575 ms |
47740 KB |
Output is correct |
12 |
Correct |
521 ms |
43208 KB |
Output is correct |
13 |
Correct |
273 ms |
644 KB |
Output is correct |
14 |
Correct |
1 ms |
388 KB |
Output is correct |
15 |
Correct |
256 ms |
640 KB |
Output is correct |
16 |
Correct |
273 ms |
572 KB |
Output is correct |
17 |
Correct |
295 ms |
516 KB |
Output is correct |
18 |
Correct |
461 ms |
12324 KB |
Output is correct |
19 |
Correct |
340 ms |
640 KB |
Output is correct |
20 |
Correct |
479 ms |
12864 KB |
Output is correct |
21 |
Correct |
307 ms |
712 KB |
Output is correct |
22 |
Correct |
337 ms |
760 KB |
Output is correct |
23 |
Correct |
402 ms |
28236 KB |
Output is correct |
24 |
Correct |
540 ms |
28344 KB |
Output is correct |
25 |
Correct |
710 ms |
55764 KB |
Output is correct |
26 |
Correct |
548 ms |
48820 KB |
Output is correct |
27 |
Correct |
314 ms |
864 KB |
Output is correct |
28 |
Correct |
426 ms |
640 KB |
Output is correct |
29 |
Correct |
258 ms |
644 KB |
Output is correct |
30 |
Correct |
693 ms |
30028 KB |
Output is correct |
31 |
Correct |
433 ms |
648 KB |
Output is correct |
32 |
Correct |
600 ms |
25548 KB |
Output is correct |
33 |
Correct |
450 ms |
724 KB |
Output is correct |
34 |
Correct |
341 ms |
880 KB |
Output is correct |
35 |
Correct |
388 ms |
900 KB |
Output is correct |
36 |
Correct |
506 ms |
30876 KB |
Output is correct |
37 |
Correct |
560 ms |
30884 KB |
Output is correct |
38 |
Correct |
720 ms |
61220 KB |
Output is correct |
39 |
Correct |
647 ms |
56508 KB |
Output is correct |
40 |
Correct |
503 ms |
928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
788 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
588 ms |
780 KB |
Output is correct |
4 |
Correct |
724 ms |
12624 KB |
Output is correct |
5 |
Correct |
39 ms |
920 KB |
Output is correct |
6 |
Correct |
567 ms |
2896 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
466 ms |
744 KB |
Output is correct |
9 |
Correct |
595 ms |
824 KB |
Output is correct |
10 |
Correct |
774 ms |
33280 KB |
Output is correct |
11 |
Correct |
798 ms |
30484 KB |
Output is correct |
12 |
Correct |
114 ms |
636 KB |
Output is correct |
13 |
Correct |
819 ms |
30468 KB |
Output is correct |
14 |
Correct |
608 ms |
744 KB |
Output is correct |
15 |
Correct |
0 ms |
388 KB |
Output is correct |
16 |
Correct |
576 ms |
784 KB |
Output is correct |
17 |
Correct |
638 ms |
752 KB |
Output is correct |
18 |
Correct |
622 ms |
748 KB |
Output is correct |
19 |
Correct |
621 ms |
736 KB |
Output is correct |
20 |
Correct |
681 ms |
752 KB |
Output is correct |
21 |
Correct |
545 ms |
788 KB |
Output is correct |
22 |
Correct |
538 ms |
788 KB |
Output is correct |
23 |
Correct |
526 ms |
776 KB |
Output is correct |
24 |
Correct |
178 ms |
656 KB |
Output is correct |
25 |
Correct |
301 ms |
616 KB |
Output is correct |
26 |
Correct |
413 ms |
16028 KB |
Output is correct |
27 |
Correct |
310 ms |
608 KB |
Output is correct |
28 |
Correct |
389 ms |
12368 KB |
Output is correct |
29 |
Correct |
249 ms |
640 KB |
Output is correct |
30 |
Correct |
246 ms |
640 KB |
Output is correct |
31 |
Correct |
283 ms |
696 KB |
Output is correct |
32 |
Correct |
405 ms |
24144 KB |
Output is correct |
33 |
Correct |
378 ms |
24248 KB |
Output is correct |
34 |
Correct |
575 ms |
47740 KB |
Output is correct |
35 |
Correct |
521 ms |
43208 KB |
Output is correct |
36 |
Correct |
273 ms |
644 KB |
Output is correct |
37 |
Correct |
1 ms |
388 KB |
Output is correct |
38 |
Correct |
256 ms |
640 KB |
Output is correct |
39 |
Correct |
273 ms |
572 KB |
Output is correct |
40 |
Correct |
295 ms |
516 KB |
Output is correct |
41 |
Correct |
461 ms |
12324 KB |
Output is correct |
42 |
Correct |
340 ms |
640 KB |
Output is correct |
43 |
Correct |
479 ms |
12864 KB |
Output is correct |
44 |
Correct |
307 ms |
712 KB |
Output is correct |
45 |
Correct |
337 ms |
760 KB |
Output is correct |
46 |
Correct |
402 ms |
28236 KB |
Output is correct |
47 |
Correct |
540 ms |
28344 KB |
Output is correct |
48 |
Correct |
710 ms |
55764 KB |
Output is correct |
49 |
Correct |
548 ms |
48820 KB |
Output is correct |
50 |
Correct |
314 ms |
864 KB |
Output is correct |
51 |
Correct |
426 ms |
640 KB |
Output is correct |
52 |
Correct |
258 ms |
644 KB |
Output is correct |
53 |
Correct |
693 ms |
30028 KB |
Output is correct |
54 |
Correct |
433 ms |
648 KB |
Output is correct |
55 |
Correct |
600 ms |
25548 KB |
Output is correct |
56 |
Correct |
450 ms |
724 KB |
Output is correct |
57 |
Correct |
341 ms |
880 KB |
Output is correct |
58 |
Correct |
388 ms |
900 KB |
Output is correct |
59 |
Correct |
506 ms |
30876 KB |
Output is correct |
60 |
Correct |
560 ms |
30884 KB |
Output is correct |
61 |
Correct |
720 ms |
61220 KB |
Output is correct |
62 |
Correct |
647 ms |
56508 KB |
Output is correct |
63 |
Correct |
503 ms |
928 KB |
Output is correct |
64 |
Correct |
521 ms |
976 KB |
Output is correct |
65 |
Correct |
840 ms |
32456 KB |
Output is correct |
66 |
Correct |
852 ms |
29064 KB |
Output is correct |
67 |
Correct |
529 ms |
960 KB |
Output is correct |
68 |
Correct |
607 ms |
952 KB |
Output is correct |
69 |
Correct |
1004 ms |
59904 KB |
Output is correct |
70 |
Correct |
939 ms |
51952 KB |
Output is correct |
71 |
Correct |
602 ms |
6452 KB |
Output is correct |
72 |
Correct |
607 ms |
1544 KB |
Output is correct |