#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int MAXN = 2100;
const int BITS_IN_DISTANCES = 11;
const int BITS_IN_VERTICES = 13;
const int INF_DISTANCE = (1 << BITS_IN_DISTANCES) - 1;
int d[MAXN];
bool vis[MAXN];
int n;
vector<pair<int, int>> adj[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int longestCommonDistance = 0;
pair<int, int> nextShortest;
int distancesKnown = 0;
int distanceReceived = 0;
int vertexReceived = 0;
int receivedBitsCount = 0;
bool gettingDistance = true; // true if receiveA gets bits for distances, false if receiveA gets bits for vertex number
void sendNumber(int number, int bits) {
for (int i = 0; i < bits; i++) {
SendA(number & (1 << i));
}
}
void sendNextShortest() {
int distance = nextShortest.first - longestCommonDistance; // subtract to fit in BITS_IN_DISTANCES bytes
sendNumber(distance, BITS_IN_DISTANCES);
}
void startSending() {
int v = pq.top().second; // both people now know that the next shortest distance is to v
pq.pop();
longestCommonDistance = d[v];
vis[v] = true;
distancesKnown++;
if (distancesKnown == n) return; // we now know all distances
for (auto p : adj[v]) {
int u = p.first;
int w = p.second;
int newDist = d[v] + w;
if (d[u] == -1 || d[u] > newDist) {
d[u] = newDist;
pq.emplace(d[u], u);
}
}
while (!pq.empty() && vis[pq.top().second]) { // don't consider if already distance known (if vis[v] is true)
pq.pop();
}
if (pq.empty()) nextShortest = {INF_DISTANCE + longestCommonDistance, n};
else nextShortest = pq.top();
sendNextShortest();
}
void distanceWasReceived() {
distanceReceived += longestCommonDistance; // because it was subtracted before sending
if (distanceReceived < nextShortest.first) { // in equality case, Azer will send vertex number
// we should now expect bits for the vertex number
gettingDistance = false;
} else {
// we have better distance, we will send the vertex number of it
gettingDistance = true;
distanceReceived = 0;
sendNumber(nextShortest.second, BITS_IN_VERTICES);
startSending();
}
}
void vertexWasReceived() {
if (d[vertexReceived] == -1 || distanceReceived < d[vertexReceived]) {
d[vertexReceived] = distanceReceived;
pq.emplace(distanceReceived, vertexReceived);
}
gettingDistance = true;
distanceReceived = 0;
vertexReceived = 0;
startSending();
}
void receiveBitForDistance(bool x) {
if (x) distanceReceived += (1 << receivedBitsCount);
receivedBitsCount++;
if (receivedBitsCount == BITS_IN_DISTANCES) { // distance was got
receivedBitsCount = 0;
distanceWasReceived();
}
}
void receiveBitForVertex(bool x) {
if (x) vertexReceived += (1 << receivedBitsCount);
receivedBitsCount++;
if (receivedBitsCount == BITS_IN_VERTICES) { // vertex was got
receivedBitsCount = 0;
vertexWasReceived();
}
}
void receiveBit(bool x) {
if (gettingDistance)
receiveBitForDistance(x);
else
receiveBitForVertex(x);
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n = N;
for (int i = 0; i < n; i++) {
d[i] = -1;
}
for (int i = 0; i < A; i++) {
adj[U[i]].emplace_back(V[i], C[i]);
adj[V[i]].emplace_back(U[i], C[i]);
}
d[0] = 0;
pq.emplace(d[0], 0);
startSending();
}
void ReceiveA(bool x) {
receiveBit(x);
}
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>
using namespace std;
namespace {
const int MAXN = 2100;
const int BITS_IN_DISTANCES = 11;
const int BITS_IN_VERTICES = 13;
const int INF_DISTANCE = (1 << BITS_IN_DISTANCES) - 1;
int d[MAXN];
bool vis[MAXN];
int n;
vector<pair<int, int>> adj[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int longestCommonDistance = 0;
pair<int, int> nextShortest;
int distancesKnown = 0;
int distanceReceived = 0;
int vertexReceived = 0;
int receivedBitsCount = 0;
bool gettingDistance = true; // true if receiveA gets bits for distances, false if receiveA gets bits for vertex number
void sendNumber(int number, int bits) {
for (int i = 0; i < bits; i++) {
SendB(number & (1 << i));
}
}
void sendNextShortest() {
int distance = nextShortest.first - longestCommonDistance; // subtract to fit in BITS_IN_DISTANCES bytes
sendNumber(distance, BITS_IN_DISTANCES);
}
void startSending() {
int v = pq.top().second; // both people now know that the next shortest distance is to v
pq.pop();
longestCommonDistance = d[v];
vis[v] = true;
distancesKnown++;
if (distancesKnown == n) return; // we now know all distances
for (auto p : adj[v]) {
int u = p.first;
int w = p.second;
int newDist = d[v] + w;
if (d[u] == -1 || d[u] > newDist) {
d[u] = newDist;
pq.emplace(d[u], u);
}
}
while (!pq.empty() && vis[pq.top().second]) { // don't consider if already distance known (if vis[v] is true)
pq.pop();
}
if (pq.empty()) nextShortest = {INF_DISTANCE + longestCommonDistance, n};
else nextShortest = pq.top();
sendNextShortest();
}
void distanceWasReceived() {
distanceReceived += longestCommonDistance; // because it was subtracted before sending
if (distanceReceived <= nextShortest.first) { // in equality case, Azer will send vertex number
// we should now expect bits for the vertex number
gettingDistance = false;
} else {
// we have better distance, we will send the vertex number of it
gettingDistance = true;
distanceReceived = 0;
sendNumber(nextShortest.second, BITS_IN_VERTICES);
startSending();
}
}
void vertexWasReceived() {
if (d[vertexReceived] == -1 || distanceReceived < d[vertexReceived]) {
d[vertexReceived] = distanceReceived;
pq.emplace(distanceReceived, vertexReceived);
}
gettingDistance = true;
distanceReceived = 0;
vertexReceived = 0;
startSending();
}
void receiveBitForDistance(bool x) {
if (x) distanceReceived += (1 << receivedBitsCount);
receivedBitsCount++;
if (receivedBitsCount == BITS_IN_DISTANCES) { // distance was got
receivedBitsCount = 0;
distanceWasReceived();
}
}
void receiveBitForVertex(bool x) {
if (x) vertexReceived += (1 << receivedBitsCount);
receivedBitsCount++;
if (receivedBitsCount == BITS_IN_VERTICES) { // vertex was got
receivedBitsCount = 0;
vertexWasReceived();
}
}
void receiveBit(bool x) {
if (gettingDistance)
receiveBitForDistance(x);
else
receiveBitForVertex(x);
}
} // namespace
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
n = N;
for (int i = 0; i < n; i++) {
d[i] = -1;
}
for (int i = 0; i < B; i++) {
adj[S[i]].emplace_back(T[i], D[i]);
adj[T[i]].emplace_back(S[i], D[i]);
}
d[0] = 0;
pq.emplace(d[0], 0);
startSending();
}
void ReceiveB(bool y) {
receiveBit(y);
}
