#include "Azer.h"
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <iostream>
#define debug(x) #x << " = " << x << '\n'
namespace {
struct Edge {
int u, v, c;
Edge() {}
Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
bool operator < (const Edge &other) const {
return c != other.c? c < other.c : u != other.u? u < other.u : v < other.v;
};
};
const int INF = 1e9 + 100;
const int logN = 11;
const int logW = 10;
std::vector<bool> memory;
std::vector<int> finalAnswer;
int num_calls = 0;
void sendInt(int x, int maxBits) {
for (int i = 0; i < maxBits; i++) {
num_calls++;
// assert(num_calls <= 55800 + 5);
SendA(x >> (maxBits - i - 1) & 1);
}
}
int receiveInt(int maxBits) {
int ret = 0;
for (int i = 0; i < maxBits; i++) {
while(memory.empty());
ret = ret * 2 + memory[0];
memory.erase(memory.begin());
}
return ret;
}
void sendEdge(Edge e) {
sendInt(e.u, logN);
sendInt(e.v, logN);
sendInt(e.c, logW);
}
Edge receiveEdge() {
Edge ret;
ret.u = receiveInt(logN);
ret.v = receiveInt(logN);
ret.c = receiveInt(logW);
return ret;
}
int phase;
int n, A;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<int> U, V, C;
std::vector<int> dist;
std::set<int> S;
Edge findEdge() {
Edge ret(0, 0, 511);
for (int u : S) {
for (auto [v, c] : g[u]) {
if (!S.count(v)) {
if (Edge(u, v, c + dist[u]) < ret) {
ret = Edge(u, v, c + dist[u]);
}
}
}
}
// if (S == std::set<int>{0, 1, 3}) {
// std::cout << " ??????? " << ret.u << ' ' << ret.v << ' ' << ret.c << '\n';
// }
if (ret.u != ret.v) {
ret.c -= dist[ret.u];
}
return ret;
}
void discover2() {
// assert(phase == 0);
auto e = findEdge();
auto e2 = receiveEdge();
sendEdge(e);
// std::cout << "AAAA \n";
// std::cout << "S: ";
// for (int x : S) {
// std::cout << x << ' ';
// }
// std::cout << '\n';
if (e.u == e.v) {
e.c = 1e9;
} else {
e.c += dist[e.u];
}
if (e2.u == e2.v) {
e2.c = 1e9;
} else {
e2.c += dist[e2.u];
}
// std::cout << e.u << ' ' << e.v << ' ' << e.c << '\n';
// std::cout << e2.u << ' ' << e2.v << ' ' << e2.c << '\n';
if (e2 < e) {
e = e2;
}
while (e.c == 1e9);
while (S.count(e.v));
// assert(e.c != 1e9);
// std::cout << " ! A added " << e.u << ' ' << e.v << ' ' << e.c << '\n';
S.insert(e.v);
dist[e.v] = e.c;
phase = 0;
}
} // namespace
void InitA(int n, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
::S.insert(0);
::g.resize(n);
for (int i = 0; i < A; i++) {
::g[U[i]].push_back({V[i], C[i]});
::g[V[i]].push_back({U[i], C[i]});
}
::n = n;
::A = A;
::U = U;
::V = V;
::C = C;
::dist.resize(n, +::INF);
::phase = 0;
::dist[0] = 0;
}
void ReceiveA(bool x) {
::memory.push_back(x);
::num_calls++;
// assert(::num_calls <= 55800 + 5);
if ((int) ::memory.size() == ::logN + ::logN + ::logW) {
::discover2();
}
}
std::vector<int> Answer() {
return ::dist;
}
#include "Baijan.h"
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <iostream>
#define debug(x) #x << " = " << x << '\n'
namespace {
struct Edge {
int u, v, c;
Edge() {}
Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
bool operator < (const Edge &other) const {
return c != other.c? c < other.c : u != other.u? u < other.u : v < other.v;
};
};
const int INF = 1e9 + 100;
const int logN = 11;
const int logW = 10;
std::vector<bool> memory;
std::vector<int> finalAnswer;
int num_calls = 0;
void sendInt(int x, int maxBits) {
for (int i = 0; i < maxBits; i++) {
num_calls++;
// assert(num_calls <= 55800 + 5);
SendB(x >> (maxBits - i - 1) & 1);
}
}
int receiveInt(int maxBits) {
int ret = 0;
for (int i = 0; i < maxBits; i++) {
while(memory.empty());
ret = ret * 2 + memory[0];
memory.erase(memory.begin());
}
return ret;
}
void sendEdge(Edge e) {
sendInt(e.u, logN);
sendInt(e.v, logN);
sendInt(e.c, logW);
}
Edge receiveEdge() {
Edge ret;
ret.u = receiveInt(logN);
ret.v = receiveInt(logN);
ret.c = receiveInt(logW);
return ret;
}
int phase;
int n, A;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<int> U, V, C;
std::vector<int> dist;
std::set<int> S;
Edge findEdge() {
Edge ret(0, 0, 511);
for (int u : S) {
for (auto [v, c] : g[u]) {
if (!S.count(v)) {
if (Edge(u, v, c + dist[u]) < ret) {
ret = Edge(u, v, c + dist[u]);
}
}
}
}
if (ret.u != ret.v) {
ret.c -= dist[ret.u];
}
return ret;
}
void discover1() {
// assert(phase == 0);
if ((int) S.size() == n) {
return;
}
auto e = findEdge();
// std::cout << "B sent " << e.u << ' ' << e.v << ' ' << e.c << '\n';
sendEdge(e);
phase = 1;
}
void discover2() {
// assert(phase == 1);
auto e = findEdge();
auto e2 = receiveEdge();
// std::cout << "BBBBB \n";
// std::cout << "S: ";
// for (int x : S) {
// std::cout << x << ' ';
// }
// std::cout << '\n';
// assert(S.count(e.u));
// assert(S.count(e2.u));
// std::cout << e.u << ' ' << e.v << ' ' << e.c << '\n';
// std::cout << e2.u << ' ' << e2.v << ' ' << e2.c << '\n';
if (e.u == e.v) {
e.c = 1e9;
} else {
e.c += dist[e.u];
}
if (e2.u == e2.v) {
e2.c = 1e9;
} else {
e2.c += dist[e2.u];
}
if (e2 < e) {
e = e2;
}
while (e.c == 1e9);
while (S.count(e.v));
// std::cout << " ! B added " << e.u << ' ' << e.v << ' ' << e.c << '\n';
S.insert(e.v);
dist[e.v] = e.c;
phase = 0;
discover1();
}
} // namespace
void InitB(int n, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
::S.insert(0);
::g.resize(n);
for (int i = 0; i < A; i++) {
::g[U[i]].push_back({V[i], C[i]});
::g[V[i]].push_back({U[i], C[i]});
}
::n = n;
::A = A;
::U = U;
::V = V;
::C = C;
::dist.resize(n, +::INF);
::phase = 0;
::dist[0] = 0;
::discover1();
}
void ReceiveB(bool x) {
::memory.push_back(x);
::num_calls++;
// assert(::num_calls <= 55800 + 5);
if ((int) ::memory.size() == ::logN + ::logN + ::logW) {
::discover2();
}
}
