#include "Azer.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';
namespace {
priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,bn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
num=min(num,511);
vi v;
for (int i=0;i<9;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendA(a);
}
void send11(int num)
{
num=min(num,2047);
vi v;
for (int i=0;i<11;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendA(a);
}
void work(int num)
{
while (bio[pq.top().y]) pq.pop();
//cout<<"A "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
if (expect11)
{
la+=ther;
res[num]=la;
bio[num]=1;
++bn;
if (bn==n) return;
for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
while (bio[pq.top().y]) pq.pop();
expect11=0;
send9(-pq.top().x-la);
}
else
{
int njre=num+la;
int more=-pq.top().x;
if (more<njre)
{
bio[pq.top().y]=1;
res[pq.top().y]=more;
++bn;
for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
la=more;
send11(pq.top().y);
if (bn==n) return;
while (bio[pq.top().y]) pq.pop();
send9(-pq.top().x-la);
}
else expect11=1,ther=num;
}
}
}
void InitA(int N, int A, vi U, vi V, vi C)
{
n=N;
for (int i=0;i<A;++i)
{
ch[U[i]].eb(V[i],C[i]);
ch[V[i]].eb(U[i],C[i]);
}
for (int i=0;i<N;++i) pq.push({-MOD,2047});
bio[0]=1;
for (auto a: ch[0]) pq.push({-a.y,a.x});
++bn;
if (bn==n) return;
send9(-pq.top().x-la);
}
void ReceiveA(bool x) {
++cn;
curn=curn*2+x;
if ((cn==9 && !expect11) || (cn==11 && expect11))
{
//cout<<"A got number "<<curn<<endl;
work(curn);
curn=0;
cn=0;
}
}
vi Answer() {
vi ans(n);
for (int k = 0; k < n; ++k) {
ans[k] = res[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(a) begin(a),end(a)
using namespace std;
namespace {
priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
num=min(num,511);
vi v;
for (int i=0;i<9;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendB(a);
}
void send11(int num)
{
num=min(num,2047);
vi v;
for (int i=0;i<11;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendB(a);
}
void work(int num)
{
while (bio[pq.top().y]) pq.pop();
//cout<<"B "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
if (expect11)
{
la+=ther;
res[num]=la;
bio[num]=1;
for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
while (bio[pq.top().y]) pq.pop();
expect11=0;
//send9(-pq.top().x-la);
}
else
{
int njre=num+la;
int more=-pq.top().x;
if (more<=njre)
{
bio[pq.top().y]=1;
res[pq.top().y]=more;
for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
send9(more-la);
la=more;
send11(pq.top().y);
while (bio[pq.top().y]) pq.pop();
}
else
{
expect11=1;
ther=num;
send9(more-la);
}
}
}
} // namespace
void InitB(int N, int A, vi U, vi V, vi C)
{
n=N;
for (int i=0;i<A;++i)
{
ch[U[i]].eb(V[i],C[i]);
ch[V[i]].eb(U[i],C[i]);
}
for (int i=0;i<N;++i) pq.push({-1e9,2047});
bio[0]=1;
for (auto a: ch[0]) pq.push({-a.y,a.x});
}
void ReceiveB(bool y) {
++cn;
curn=curn*2+y;
if ((cn==9 && !expect11) || (cn==11 && expect11))
{
//cout<<"B got number "<<curn<<endl;
work(curn);
curn=0;
cn=0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
940 ms |
30008 KB |
Output is correct |
2 |
Correct |
20 ms |
29184 KB |
Output is correct |
3 |
Correct |
1011 ms |
29952 KB |
Output is correct |
4 |
Correct |
1380 ms |
48136 KB |
Output is correct |
5 |
Correct |
82 ms |
30192 KB |
Output is correct |
6 |
Correct |
1002 ms |
33832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
29184 KB |
Output is correct |
2 |
Correct |
874 ms |
29800 KB |
Output is correct |
3 |
Correct |
1070 ms |
30168 KB |
Output is correct |
4 |
Correct |
1950 ms |
83424 KB |
Output is correct |
5 |
Correct |
2028 ms |
85448 KB |
Output is correct |
6 |
Correct |
306 ms |
29760 KB |
Output is correct |
7 |
Correct |
2120 ms |
85456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1652 ms |
30176 KB |
Output is correct |
2 |
Correct |
27 ms |
29216 KB |
Output is correct |
3 |
Correct |
1604 ms |
30176 KB |
Output is correct |
4 |
Correct |
1056 ms |
30120 KB |
Output is correct |
5 |
Correct |
908 ms |
30360 KB |
Output is correct |
6 |
Correct |
1154 ms |
29904 KB |
Output is correct |
7 |
Correct |
982 ms |
30008 KB |
Output is correct |
8 |
Correct |
1118 ms |
29920 KB |
Output is correct |
9 |
Correct |
1358 ms |
29760 KB |
Output is correct |
10 |
Correct |
1150 ms |
29992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
546 ms |
29728 KB |
Output is correct |
2 |
Correct |
430 ms |
29920 KB |
Output is correct |
3 |
Correct |
802 ms |
53104 KB |
Output is correct |
4 |
Correct |
572 ms |
30016 KB |
Output is correct |
5 |
Correct |
794 ms |
45400 KB |
Output is correct |
6 |
Correct |
730 ms |
29752 KB |
Output is correct |
7 |
Correct |
540 ms |
29720 KB |
Output is correct |
8 |
Correct |
660 ms |
29920 KB |
Output is correct |
9 |
Correct |
912 ms |
75176 KB |
Output is correct |
10 |
Correct |
1216 ms |
75008 KB |
Output is correct |
11 |
Correct |
1854 ms |
113840 KB |
Output is correct |
12 |
Correct |
1406 ms |
107880 KB |
Output is correct |
13 |
Correct |
750 ms |
30288 KB |
Output is correct |
14 |
Correct |
24 ms |
29184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
546 ms |
29728 KB |
Output is correct |
2 |
Correct |
430 ms |
29920 KB |
Output is correct |
3 |
Correct |
802 ms |
53104 KB |
Output is correct |
4 |
Correct |
572 ms |
30016 KB |
Output is correct |
5 |
Correct |
794 ms |
45400 KB |
Output is correct |
6 |
Correct |
730 ms |
29752 KB |
Output is correct |
7 |
Correct |
540 ms |
29720 KB |
Output is correct |
8 |
Correct |
660 ms |
29920 KB |
Output is correct |
9 |
Correct |
912 ms |
75176 KB |
Output is correct |
10 |
Correct |
1216 ms |
75008 KB |
Output is correct |
11 |
Correct |
1854 ms |
113840 KB |
Output is correct |
12 |
Correct |
1406 ms |
107880 KB |
Output is correct |
13 |
Correct |
750 ms |
30288 KB |
Output is correct |
14 |
Correct |
24 ms |
29184 KB |
Output is correct |
15 |
Correct |
734 ms |
29696 KB |
Output is correct |
16 |
Correct |
786 ms |
29696 KB |
Output is correct |
17 |
Correct |
456 ms |
29696 KB |
Output is correct |
18 |
Correct |
906 ms |
46016 KB |
Output is correct |
19 |
Correct |
699 ms |
29736 KB |
Output is correct |
20 |
Correct |
938 ms |
46168 KB |
Output is correct |
21 |
Correct |
587 ms |
29920 KB |
Output is correct |
22 |
Correct |
658 ms |
30176 KB |
Output is correct |
23 |
Correct |
1140 ms |
80872 KB |
Output is correct |
24 |
Correct |
1652 ms |
80920 KB |
Output is correct |
25 |
Correct |
2542 ms |
131192 KB |
Output is correct |
26 |
Correct |
1508 ms |
117000 KB |
Output is correct |
27 |
Correct |
572 ms |
30272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
546 ms |
29728 KB |
Output is correct |
2 |
Correct |
430 ms |
29920 KB |
Output is correct |
3 |
Correct |
802 ms |
53104 KB |
Output is correct |
4 |
Correct |
572 ms |
30016 KB |
Output is correct |
5 |
Correct |
794 ms |
45400 KB |
Output is correct |
6 |
Correct |
730 ms |
29752 KB |
Output is correct |
7 |
Correct |
540 ms |
29720 KB |
Output is correct |
8 |
Correct |
660 ms |
29920 KB |
Output is correct |
9 |
Correct |
912 ms |
75176 KB |
Output is correct |
10 |
Correct |
1216 ms |
75008 KB |
Output is correct |
11 |
Correct |
1854 ms |
113840 KB |
Output is correct |
12 |
Correct |
1406 ms |
107880 KB |
Output is correct |
13 |
Correct |
750 ms |
30288 KB |
Output is correct |
14 |
Correct |
24 ms |
29184 KB |
Output is correct |
15 |
Correct |
734 ms |
29696 KB |
Output is correct |
16 |
Correct |
786 ms |
29696 KB |
Output is correct |
17 |
Correct |
456 ms |
29696 KB |
Output is correct |
18 |
Correct |
906 ms |
46016 KB |
Output is correct |
19 |
Correct |
699 ms |
29736 KB |
Output is correct |
20 |
Correct |
938 ms |
46168 KB |
Output is correct |
21 |
Correct |
587 ms |
29920 KB |
Output is correct |
22 |
Correct |
658 ms |
30176 KB |
Output is correct |
23 |
Correct |
1140 ms |
80872 KB |
Output is correct |
24 |
Correct |
1652 ms |
80920 KB |
Output is correct |
25 |
Correct |
2542 ms |
131192 KB |
Output is correct |
26 |
Correct |
1508 ms |
117000 KB |
Output is correct |
27 |
Correct |
572 ms |
30272 KB |
Output is correct |
28 |
Correct |
920 ms |
29696 KB |
Output is correct |
29 |
Correct |
698 ms |
29696 KB |
Output is correct |
30 |
Correct |
1464 ms |
72848 KB |
Output is correct |
31 |
Correct |
674 ms |
29816 KB |
Output is correct |
32 |
Correct |
1380 ms |
65920 KB |
Output is correct |
33 |
Correct |
734 ms |
30072 KB |
Output is correct |
34 |
Correct |
750 ms |
30224 KB |
Output is correct |
35 |
Correct |
710 ms |
30208 KB |
Output is correct |
36 |
Correct |
1218 ms |
86416 KB |
Output is correct |
37 |
Correct |
1756 ms |
86200 KB |
Output is correct |
38 |
Correct |
2160 ms |
141176 KB |
Output is correct |
39 |
Correct |
2296 ms |
130560 KB |
Output is correct |
40 |
Correct |
924 ms |
30816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
940 ms |
30008 KB |
Output is correct |
2 |
Correct |
20 ms |
29184 KB |
Output is correct |
3 |
Correct |
1011 ms |
29952 KB |
Output is correct |
4 |
Correct |
1380 ms |
48136 KB |
Output is correct |
5 |
Correct |
82 ms |
30192 KB |
Output is correct |
6 |
Correct |
1002 ms |
33832 KB |
Output is correct |
7 |
Correct |
22 ms |
29184 KB |
Output is correct |
8 |
Correct |
874 ms |
29800 KB |
Output is correct |
9 |
Correct |
1070 ms |
30168 KB |
Output is correct |
10 |
Correct |
1950 ms |
83424 KB |
Output is correct |
11 |
Correct |
2028 ms |
85448 KB |
Output is correct |
12 |
Correct |
306 ms |
29760 KB |
Output is correct |
13 |
Correct |
2120 ms |
85456 KB |
Output is correct |
14 |
Correct |
1652 ms |
30176 KB |
Output is correct |
15 |
Correct |
27 ms |
29216 KB |
Output is correct |
16 |
Correct |
1604 ms |
30176 KB |
Output is correct |
17 |
Correct |
1056 ms |
30120 KB |
Output is correct |
18 |
Correct |
908 ms |
30360 KB |
Output is correct |
19 |
Correct |
1154 ms |
29904 KB |
Output is correct |
20 |
Correct |
982 ms |
30008 KB |
Output is correct |
21 |
Correct |
1118 ms |
29920 KB |
Output is correct |
22 |
Correct |
1358 ms |
29760 KB |
Output is correct |
23 |
Correct |
1150 ms |
29992 KB |
Output is correct |
24 |
Correct |
546 ms |
29728 KB |
Output is correct |
25 |
Correct |
430 ms |
29920 KB |
Output is correct |
26 |
Correct |
802 ms |
53104 KB |
Output is correct |
27 |
Correct |
572 ms |
30016 KB |
Output is correct |
28 |
Correct |
794 ms |
45400 KB |
Output is correct |
29 |
Correct |
730 ms |
29752 KB |
Output is correct |
30 |
Correct |
540 ms |
29720 KB |
Output is correct |
31 |
Correct |
660 ms |
29920 KB |
Output is correct |
32 |
Correct |
912 ms |
75176 KB |
Output is correct |
33 |
Correct |
1216 ms |
75008 KB |
Output is correct |
34 |
Correct |
1854 ms |
113840 KB |
Output is correct |
35 |
Correct |
1406 ms |
107880 KB |
Output is correct |
36 |
Correct |
750 ms |
30288 KB |
Output is correct |
37 |
Correct |
24 ms |
29184 KB |
Output is correct |
38 |
Correct |
734 ms |
29696 KB |
Output is correct |
39 |
Correct |
786 ms |
29696 KB |
Output is correct |
40 |
Correct |
456 ms |
29696 KB |
Output is correct |
41 |
Correct |
906 ms |
46016 KB |
Output is correct |
42 |
Correct |
699 ms |
29736 KB |
Output is correct |
43 |
Correct |
938 ms |
46168 KB |
Output is correct |
44 |
Correct |
587 ms |
29920 KB |
Output is correct |
45 |
Correct |
658 ms |
30176 KB |
Output is correct |
46 |
Correct |
1140 ms |
80872 KB |
Output is correct |
47 |
Correct |
1652 ms |
80920 KB |
Output is correct |
48 |
Correct |
2542 ms |
131192 KB |
Output is correct |
49 |
Correct |
1508 ms |
117000 KB |
Output is correct |
50 |
Correct |
572 ms |
30272 KB |
Output is correct |
51 |
Correct |
920 ms |
29696 KB |
Output is correct |
52 |
Correct |
698 ms |
29696 KB |
Output is correct |
53 |
Correct |
1464 ms |
72848 KB |
Output is correct |
54 |
Correct |
674 ms |
29816 KB |
Output is correct |
55 |
Correct |
1380 ms |
65920 KB |
Output is correct |
56 |
Correct |
734 ms |
30072 KB |
Output is correct |
57 |
Correct |
750 ms |
30224 KB |
Output is correct |
58 |
Correct |
710 ms |
30208 KB |
Output is correct |
59 |
Correct |
1218 ms |
86416 KB |
Output is correct |
60 |
Correct |
1756 ms |
86200 KB |
Output is correct |
61 |
Correct |
2160 ms |
141176 KB |
Output is correct |
62 |
Correct |
2296 ms |
130560 KB |
Output is correct |
63 |
Correct |
924 ms |
30816 KB |
Output is correct |
64 |
Correct |
906 ms |
30536 KB |
Output is correct |
65 |
Correct |
1928 ms |
75312 KB |
Output is correct |
66 |
Correct |
1858 ms |
69304 KB |
Output is correct |
67 |
Correct |
1032 ms |
30248 KB |
Output is correct |
68 |
Correct |
1424 ms |
30440 KB |
Output is correct |
69 |
Correct |
2580 ms |
139376 KB |
Output is correct |
70 |
Correct |
2306 ms |
122088 KB |
Output is correct |
71 |
Correct |
1168 ms |
40024 KB |
Output is correct |
72 |
Correct |
1138 ms |
30776 KB |
Output is correct |