#include "migrations.h" using namespace std; #include <bits/stdc++.h> vector<vector<int>> adj; vector<int> dist_from_0; void dfs(int u){ for(int v : adj[u]){ dist_from_0[v] = dist_from_0[u] + 1; dfs(v); } } int ipow(int base, int exp) { int result = 1; while (exp > 0) { if (exp & 1) result *= base; base *= base; exp >>= 1; } return result; } int furtherest = 0; 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); return 0; } adj[Pi].push_back(i); if(i < 9992) return 0; if(i == 9992){ int max_dist = 0; dfs(0); for(int iz = 0; iz < dist_from_0.size(); iz ++){ if(dist_from_0[iz] > max_dist){ max_dist = dist_from_0[iz]; furtherest = iz; } } return (furtherest / ipow(5, 5)) % 5; } if(i == 9993){ return (furtherest / ipow(5, 4)) % 5; } if(i == 9994){ return (furtherest / ipow(5, 3)) % 5; } if(i == 9995){ return (furtherest / ipow(5, 2)) % 5; } if(i == 9996){ return (furtherest / ipow(5, 1)) % 5; } if(i == 9997){ return (furtherest) % 5; } if(i == 9998){ int max_dist = 0; int furth = 0; dfs(0); for(int iz = 0; iz < dist_from_0.size(); iz ++){ if(dist_from_0[iz] > max_dist){ max_dist = dist_from_0[iz]; furth = iz; } } if(furth == furtherest){ return 0; } furtherest = furth; if(furtherest == 9993){ return 1; } if(furtherest == 9994){ return 2; } if(furtherest == 9995){ return 3; } if(furtherest == 9996){ return 4; } } if(i == 9999){ int max_dist = 0; int furth = 0; dfs(0); for(int iz = 0; iz < dist_from_0.size(); iz ++){ if(dist_from_0[iz] > max_dist){ max_dist = dist_from_0[iz]; furth = iz; } } furtherest = furth; if(furtherest == 9997){ return 1; } if(furtherest == 9998){ return 2; } if(furtherest == 9999){ return 3; } } return 0; } std::pair<int, int> longest_path(std::vector<int> S) { if(S[9998] == 0 && S[9999 == 0]){ int res = 0; res += S[9992] * ipow(5, 5); res += S[9993] * ipow(5, 4); res += S[9994] * ipow(5, 3); res += S[9995] * ipow(5, 2); res += S[9996] * ipow(5, 1); res += S[9997] * ipow(5, 0); return {0, res}; } if(S[9999] == 0){ return {0, S[9998] + 9992}; } return {0, S.back() + 9996}; } /* g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp 6 0 0 2 2 3 */