#include "migrations.h"
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> adj;
std::vector<int> parent;
int diameter_u, diameter_v, diameter_dist;
std::pair<int, int> bfs_farthest(int start, int n) {
std::vector<int> dist(n, -1);
std::vector<int> queue;
dist[start] = 0;
queue.push_back(start);
int farthest = start;
int max_dist = 0;
for (size_t idx = 0; idx < queue.size(); idx++) {
int u = queue[idx];
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue.push_back(v);
if (dist[v] > max_dist) {
max_dist = dist[v];
farthest = v;
}
}
}
}
return {farthest, max_dist};
}
int send_message(int N, int i, int Pi) {
if (i == 1) {
// Initialize
adj.clear();
adj.resize(N);
parent.clear();
parent.resize(N);
parent[0] = -1;
diameter_u = 0;
diameter_v = 0;
diameter_dist = 0;
}
// Add edge
adj[i].push_back(Pi);
adj[Pi].push_back(i);
parent[i] = Pi;
// Find diameter: BFS from one endpoint, then BFS from farthest point
auto [far1, dist1] = bfs_farthest(diameter_u, N);
auto [far2, dist2] = bfs_farthest(far1, N);
int old_u = diameter_u;
int old_v = diameter_v;
int old_dist = diameter_dist;
diameter_u = far1;
diameter_v = far2;
diameter_dist = dist2;
// Send message only if diameter changed
if (diameter_dist > old_dist) {
// Encode both endpoints
int msg = diameter_u * 10000 + diameter_v;
return msg;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int last_msg = 0;
for (int i = 1; i < (int)S.size(); i++) {
if (S[i] > 0) {
last_msg = S[i];
}
}
if (last_msg == 0) {
return {0, 0};
}
int u = last_msg / 10000;
int v = last_msg % 10000;
return {u, v};
}
