#include "migrations.h"
#include <vector>
#include <algorithm>
#include <cmath>
// Globals for the research team's (send_message) phase
namespace {
// Constants for the messaging protocol
const int BITS_PER_NODE = 14;
const int MSGS_PER_NODE = (BITS_PER_NODE + 1) / 2; // Each message (1-4) carries 2 bits
const int TOTAL_MSGS_PER_PAIR = 2 * MSGS_PER_NODE;
// Tree-related data structures
int N_val;
std::vector<int> parent;
std::vector<int> depth;
std::vector<std::vector<int>> up;
int log_N;
// Current diameter endpoints
int current_U;
int current_V;
// Payload for the final transmission
std::vector<int> msg_payload;
}
// Initializes global state for the research team
void init_globals(int N) {
N_val = N;
log_N = (N > 1) ? floor(log2(N)) + 1 : 1;
parent.assign(N, -1);
depth.assign(N, 0);
up.assign(N, std::vector<int>(log_N, 0));
current_U = 0;
current_V = 0;
}
// Finds the Lowest Common Ancestor of two nodes
int get_lca(int u, int v) {
if (depth[u] < depth[v]) std::swap(u, v);
for (int j = log_N - 1; j >= 0; --j) {
if (depth[u] - (1 << j) >= depth[v]) {
u = up[u][j];
}
}
if (u == v) return u;
for (int j = log_N - 1; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return parent[u];
}
// Calculates distance between two nodes in the tree
int get_dist(int u, int v) {
if (u == -1 || v == -1) return -1;
int lca = get_lca(u, v);
return depth[u] + depth[v] - 2 * depth[lca];
}
// Research team's procedure
int send_message(int N, int i, int Pi) {
if (i == 1) {
init_globals(N);
}
// Update tree structure with the new node i
parent[i] = Pi;
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int j = 1; j < log_N; ++j) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
// Online update of the diameter
int dist_UV = get_dist(current_U, current_V);
int dist_iU = get_dist(i, current_U);
int dist_iV = get_dist(i, current_V);
if (dist_iU > dist_UV && dist_iU >= dist_iV) {
current_V = i;
std::swap(current_U, current_V);
} else if (dist_iV > dist_UV) {
current_U = i;
}
// At a pre-determined point, compute the current diameter and schedule it for transmission
int decision_idx = (N - 1) - TOTAL_MSGS_PER_PAIR;
if (i == decision_idx) {
int U_to_send = current_U;
int V_to_send = current_V;
if (U_to_send > V_to_send) std::swap(U_to_send, V_to_send);
msg_payload.clear();
for (int k = 0; k < MSGS_PER_NODE; ++k) {
int u_bits = (U_to_send >> (2 * k)) & 3;
msg_payload.push_back(u_bits + 1);
}
for (int k = 0; k < MSGS_PER_NODE; ++k) {
int v_bits = (V_to_send >> (2 * k)) & 3;
msg_payload.push_back(v_bits + 1);
}
}
// Send the scheduled messages in the final slots
if (i > decision_idx) {
int msg_idx = i - (decision_idx + 1);
if (msg_idx >= 0 && msg_idx < msg_payload.size()) {
return msg_payload[msg_idx];
}
}
return 0; // No message sent
}
// Museum's procedure
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
if (N == 0) return {0, 0};
// The sender sends messages only in the last few slots.
// We collect messages from these specific slots.
std::vector<int> received_msgs;
int start_idx = (N - 1) - TOTAL_MSGS_PER_PAIR + 1;
if (start_idx < 1) start_idx = 1;
for (int i = start_idx; i < N; ++i) {
received_msgs.push_back(S[i]);
}
if (received_msgs.empty()) return {0, 0};
int U = 0, V = 0;
// Decode the first node ID
int msgs_for_U = std::min((int)received_msgs.size(), MSGS_PER_NODE);
for(int k = 0; k < msgs_for_U; ++k) {
if (received_msgs[k] == 0) continue;
int bits = received_msgs[k] - 1;
U |= (bits << (2 * k));
}
// Decode the second node ID
if (received_msgs.size() > MSGS_PER_NODE) {
for(size_t k = 0; k < received_msgs.size() - MSGS_PER_NODE; ++k) {
if (received_msgs[k + MSGS_PER_NODE] == 0) continue;
int bits = received_msgs[k + MSGS_PER_NODE] - 1;
V |= (bits << (2 * k));
}
}
if (U > V) std::swap(U, V);
return {U, V};
}
