#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int par[maxn];
vector<int>g[maxn];
pair<int,int>diam = {-1,-1};
void dfs(int st, int dep[], int p, int d){
dep[st]=d;
for(int i : g[st]){
if(i==p)
continue;
dfs(i,dep,st,d+1);
}
}
pair<int,int> find_diam(){
int dep[maxn];
fill(dep,dep+maxn,-1);
dfs(0,dep,-1,0);
int u = max_element(dep,dep+maxn)-dep;
dfs(u,dep,-1,0);
int v = max_element(dep,dep+maxn)-dep;
if(u>v){
swap(u,v);
}
return {u,v};
}
string base4conv(int x){
string ans = "";
while(x){
ans+=to_string(x%4);
x/=4;
}
while(ans.size()<30){
ans+="0";
}
//reverse(ans.begin(),ans.end());
return ans;
}
int u;
int send_message(int n, int i, int Pi) {
par[i]=Pi;
g[i].push_back(Pi);
g[Pi].push_back(i);
if(i==n-21){
diam=find_diam();
string b = base4conv(diam.first);
return b[0]-'0';
}
else if(n-21<i&&i<n-14){
//transferring u rn.
pair<int,int>curr = find_diam();
if(curr.first==diam.first){
//u unchanged, continue
diam=curr;
string b = base4conv(diam.first);
if(u<n-21){
u=diam.first;
}
return (b[i-(n-21)]-'0');
}
else{
diam=curr;
u=i;
return 4;
}
}
else if(n-14<=i){
//u has been transferred.
pair<int,int>curr = find_diam();
if(curr.first == u && curr.second == i){
//nice, lets do 2
diam=curr;
return 2;
}
else{
//u,v
int v = diam.second;
if(u==v){
v=diam.first;
}
if(diam==curr){
//next bit of v in 0,1
int z = i-(n-14);
if((1<<z)&v){
return 1;
}
else{
return 0;
}
}
else{
//{v,i}
diam=curr;
int z = i-(n-14);
u=i;
if((1<<z)&v){
return 4;
}
else{
return 3;
}
}
}
}
return 0;
}
pair<int, int> longest_path(vector<int> S) {
int n = S.size();
int u=0,v=0;
for(int i = n-21;i<n-14;i++){
if(S[i]==4){
u=i;
}
else{
if(u<n-21){
//doing base 4 bits.
u+=S[i]*(1<<(2*(i-(n-21))));
}
}
}
//u is found
bool sent = 0;
for(int i = n-14;i<n;i++){
if(S[i]==0){
if(sent){
continue;
}
}
else if(S[i]==1){
if(sent){
continue;
}
v+=(1<<(i-(n-14)));
}
else if(S[i]==2){
v=i;
sent=1;
}
else if(S[i]==3){
u=i;
}
else if(S[i]==4){
u=i;
if(sent)
continue;
v+=(1<<(i-(n-14)));
}
}
return {u,v};
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |