#include "migrations.h"
using namespace std;
#include <bits/stdc++.h>
vector<vector<int>> adj;
vector<int> dist_from_0;
int farthest_from(int src) {
int n = (int)adj.size();
vector<int> dist(n, -1);
queue<int> q;
dist[src] = 0;
q.push(src);
int best = src;
while(!q.empty()) {
int u = q.front(); q.pop();
if(dist[u] > dist[best]) best = u;
for(int v : adj[u]) if(dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
return best;
}
int furtherest = 0;
int end_1;
int end_2;
set<int> seen;
int send_message(int N, int i, int Pi) {
if(i == 1){
adj.resize(N);
dist_from_0.resize(N, 0);
adj[Pi].push_back(1);
adj[1].push_back(0);
return 0;
}
adj[Pi].push_back(i);
adj[i].push_back(Pi);
if(i < N - 3) return 0;
if(i == N - 3){
end_1 = farthest_from(0);
end_2 = farthest_from(end_1);
if(end_1 > end_2){
int temp = end_1;
end_1 = end_2;
end_2 = temp;
}
seen.insert(end_1);
seen.insert(end_2);
return end_1;
}
if(i == N - 2){
return end_2;
}
if(i == N - 1){
int new_end1 = farthest_from(0);
int new_end2 = farthest_from(new_end1);
vector<int> new_ends;
new_ends = {new_end1, new_end2};
sort(new_ends.begin(), new_ends.end());
int res = 0;
if(seen.count(new_ends[0]) && seen.count(new_ends[1])){
return 0; // none replaced
}
if(new_ends[0] == N - 2 && new_ends[1] == N - 1){
return 2 * N;
} // both replaced
// one replaced
if(new_ends[0] <= N - 3 && new_ends[1] >= N - 2){
res = new_ends[0];
// just need to communicate the node that was replaced
//cout << new_end1 << " " << new_end2;
if(res == end_1){
return new_ends[1];
} else {
return new_ends[1] - 5;
}
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
if(S.back() == 0){
return {S[N-3], S[N-2]};
}
if(S.back() == 2*N){
return {N-2, N-1};
}
if(S.back() < N && S.back() >= N - 3){
return {S[N-3], S.back()};
} else {
return {S[N-2], S.back() + 5};
}
return {0, 0};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp
8
0 0 2 2 3 1 6
*/
