Submission #1254498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254498		TadijaSebez	Migrations (IOI25_migrations)	C++20	83.69 / 100	32 ms	1000 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=10050;
const int LOG=14;
int par[N][LOG],dep[N];
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=LOG-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
    for(int i=LOG-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
    return u==v?v:par[v][0];
}
int Dist(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}

pair<int,int> diam,savedDiam;
int offs;
int send_message(int n, int u, int p) {
    if(u==1){
        dep[0]=1;
        diam={0,0};
    }
    par[u][0]=p;
    dep[u]=dep[p]+1;
    for(int i=1;i<LOG;i++){
        par[u][i]=par[par[u][i-1]][i-1];
    }
    if(n<=LOG+4){
        int upd=2;
        if(Dist(diam.first,diam.second)<Dist(diam.second,u)){
            diam.first=u;
            upd=0;
        }else if(Dist(diam.first,diam.second)<Dist(diam.first,u)){
            diam.second=u;
            upd=1;
        }
        return upd;
    }else{
        if(u==n-LOG-4){
            savedDiam=diam;
            //printf("Saved diam: %i %i\n",savedDiam.first,savedDiam.second);
        }
        int upd=2;
        if(Dist(diam.first,diam.second)<Dist(diam.second,u)){
            diam.first=u;
            upd=0;
        }else if(Dist(diam.first,diam.second)<Dist(diam.first,u)){
            diam.second=u;
            upd=1;
        }

        if(u<n-LOG-4)return 0;
        //printf("Here %i\n",u);
        if(u<n-LOG/2-4){
            int idx=(u-(n-LOG-4))*2;
            int bit=savedDiam.first>>idx&3;
            if(upd==2)return bit;
            if(upd==0)return 4;
            if(upd==1)savedDiam.second=diam.second;
            return bit;
        }else if(u<n-4){
            int idx=(u-(n-LOG/2-4))*2;
            int bit=savedDiam.second>>idx&3;
            if(upd==2)return bit;
            if(upd==1)return 4;
            return bit;
        }else{
            if(u==n-4){
                offs=n-4-diam.first;
                if(offs>8)offs=8;
            }
            int idx=u-(n-4);
            int bit=offs>>idx&1;
            if(upd==2)return bit;
            if(upd==0)return 4;
            return 2+bit;
        }
    }
}

pair<int, int> longest_path(vector<int> S) {
    pair<int,int> ans={0,0};
    int n=S.size();
    //printf("n = %i\n",n,2*LOG);
    if(n<=LOG+4){
        for(int i=1;i<n;i++){
            if(S[i]==0){
                ans.first=i;
            }else if(S[i]==1){
                ans.second=i;
            }
        }
        return ans;
    }else{
        vector<pair<int,int>> changes;
        int L=0,R=0;
        for(int i=n-LOG-4;i<n-LOG/2-4;i++){
            int idx=(i-(n-LOG-4))*2;
            //printf("L %i %i\n",idx,S[i]);
            if(S[i]<4){
                L+=S[i]<<idx;
            }
            if(S[i]==4){
                changes.pb({i,0});
            }
        }
        for(int i=n-LOG/2-4;i<n-4;i++){
            int idx=(i-(n-LOG/2-4))*2;
            //printf("R %i %i\n",idx,S[i]);
            if(S[i]<4){
                R+=S[i]<<idx;
            }
            if(S[i]==4){
                changes.pb({i,1});
            }
        }
        int D=0;
        for(int i=n-4;i<n;i++){
            int idx=(i-(n-4));
            if(S[i]==0 || S[i]==2){
                // bit je 0
            }else if(S[i]==1 || S[i]==3){
                D+=1<<idx;
            }
        }
        if(D!=8){
            changes.pb({n-4-D,0});
        }
        for(int i=n-4;i<n;i++){
            if(S[i]==4){
                changes.pb({i,0});
            }else if(S[i]==2 || S[i]==3){
                changes.pb({i,1});
            }
        }
        //printf("L: %i, R: %i\n",L,R);
        for(auto upd:changes){
            if(upd.second==0)L=upd.first;
            else R=upd.first;
        }
        return {L,R};
    }
}

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