#include "Azer.h"
// #include <iostream>
#include <vector>
#include <set>
using namespace std;
namespace {
const int M = 1<<11;
vector<pair<int, int>> nei[M];
vector<int> Ans;
set<pair<int, int>> st;
int L, K, num, Last, cnt = 0;
pair<int, int> Nxt;
}
void Asends(int v, int k){
for (int i=k-1;i+1;i--)
SendA(!!(v & (1<<i)));
}
pair<int, int> getMinA(){
auto [mn, u] = *begin(st);
if (mn == Ans[u])
return {mn, u};
st.erase(begin(st));
return getMinA();
}
void relaxA(int mn, int u){
Last = mn, cnt ++;
st.erase({mn, u});
Ans[u] = mn;
// cout<<mn<<' '<<u<<endl<<endl
for (auto [i, w] : nei[u]){
if (Ans[i] > Ans[u] + w)
Ans[i] = Ans[u] + w,
st.insert({Ans[i], i});
}
if (cnt == Ans.size())
return;
Nxt = getMinA();
Asends(min(510, Nxt.first - Last), 9);
L = 9, K = 0, num = 0;
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
Ans.resize(N, 1e9);
Ans[0] = 0;
for (int i=0;i<A;i++){
nei[U[i]].push_back({V[i], C[i]});
nei[V[i]].push_back({U[i], C[i]});
}
for (int i=0;i<N;i++)
st.insert({Ans[i], i});
relaxA(0, 0);
}
void ReceiveA(bool x) {
num += num + x, K++;
if (K == L){
if (L == 9 and num == 511){
Asends(Nxt.second, 11);
relaxA(Nxt.first, Nxt.second);
}
else if (L == 9){
Nxt.first = num + Last;
K = 0, num = 0, L = 11;
}
else{
Nxt.second = num;
relaxA(Nxt.first, Nxt.second);
}
}
}
vector<int> Answer() {
return Ans;
}
#include "Baijan.h"
#include <vector>
#include <set>
using namespace std;
namespace {
const int M = 1<<11;
vector<pair<int, int>> nei[M];
vector<int> Ans;
set<pair<int, int>> st;
int L, K, num, Last, cnt = 0;
pair<int, int> Nxt;
}
void Bsends(int v, int k){
for (int i=k-1;i+1;i--)
SendB(!!(v & (1<<i)));
}
pair<int, int> getMinB(){
auto [mn, u] = *begin(st);
if (mn == Ans[u])
return {mn, u};
st.erase(begin(st));
return getMinB();
}
void relaxB(int mn, int u){
Last = mn, cnt ++;
st.erase({mn, u});
Ans[u] = mn;
for (auto [i, w] : nei[u]){
if (Ans[i] > Ans[u] + w)
Ans[i] = Ans[u] + w,
st.insert({Ans[i], i});
}
if (cnt == Ans.size())
return;
Nxt = getMinB();
L = 9, K = 0, num = 0;
}
void InitB(int N, int B, vector<int> U, vector<int> V, vector<int> C) {
Ans.resize(N, 1e9);
Ans[0] = 0;
for (int i=0;i<B;i++){
nei[U[i]].push_back({V[i], C[i]});
nei[V[i]].push_back({U[i], C[i]});
}
for (int i=0;i<N;i++)
st.insert({Ans[i], i});
relaxB(0, 0);
}
void ReceiveB(bool y) {
num += num + y, K ++;
if (K == L){
if (L == 9 and num > Nxt.first - Last){
Bsends(Nxt.first - Last, 9);
Bsends(Nxt.second, 11);
relaxB(Nxt.first, Nxt.second);
}
else if (L == 9){
Bsends(511, 9);
Nxt.first = num + Last;
K = 0, num = 0, L = 11;
}
else{
Nxt.second = num;
relaxB(Nxt.first, Nxt.second);
}
}
}
