Submission #1259456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259456		Aviansh	Migrations (IOI25_migrations)	C++20	79.12 / 100	35 ms	1244 KiB

migrations

#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};
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 49.1152 / 70