#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] + N; } } } 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){ return {S[N-3], S.back()}; } else { return {S[N-2], S.back() - N}; } 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 */