#include "migrations.h" using namespace std; #include <bits/stdc++.h> vector<vector<int>> adj; vector<int> dist_from_0; void dfs(int u, vector<int>& dist){ for(int v : adj[u]){ dist[v] = dist[u] + 1; dfs(v, dist); } } int furtherest_node_from(int u){ vector<int> dist(adj.size(), 0); int max_dist = 0; int far = 0; dfs(u, dist); for(int iz = 0; iz < dist_from_0.size(); iz ++){ if(dist[iz] > max_dist){ max_dist = dist_from_0[iz]; far = iz; } } return far; } 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 end_1; int end_2; //vector<int> ends; 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 < 9997) return 0; if(i == 9997){ end_1 = furtherest_node_from(0); end_2 = furtherest_node_from(end_1); if(end_1 > end_2){ int temp = end_1; end_1 = end_2; end_2 = temp; } //ends = {end_1, end_2}; //sort(ends.begin(), ends.end()); return end_1; } if(i == 9998){ // return end_2; } if(i == 9999){ int new_end1 = furtherest_node_from(0); int new_end2 = furtherest_node_from(new_end1); vector<int> new_ends; new_ends = {new_end1, new_end2}; sort(new_ends.begin(), new_ends.end()); int res = 0; if(new_ends[0] == 9998){ res += 1000; } if(new_ends[0] == 9999){ res += 2000; } if(new_ends[1] == 9998){ res += 100; } if(new_ends[1] == 9999){ res += 200; } return res; } return 0; } std::pair<int, int> longest_path(std::vector<int> S) { if(S.back() == 0){ return {S[9997], S[9998]}; } pair<int, int> res = {S[9997], S[9998]}; if(S.back() % 1000 == 1){ res.first = 9998; } if(S.back() % 1000 == 2){ res.first = 9999; } if(S.back() % 100 == 1){ res.second = 9998; } if(S.back() % 100 == 2){ res.second = 9999; } return res; } /* g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp 6 0 0 2 2 3 */