Submission #1264393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264393		StefanSebez	Migrations (IOI25_migrations)	C++20	72.89 / 100	31 ms	1696 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=10050,lg=14,K=28;
vector<int>E[N];
int par[N+50][lg+2],depth[N+50];
int LCA(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    for(int i=lg;i>=0;i--) if(depth[par[u][i]]>=depth[v]) u=par[u][i];if(u==v) return u;
    for(int i=lg;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
/*int dist[N];
void DFS(int u,int p=-1){
    if(p==-1) dist[u]=0;
    else dist[u]=dist[p]+1;
    for(auto i:E[u]) if(i!=p) DFS(i,u);
}
int Dist1(int u,int v){
    DFS(u);
    return dist[v];
}*/
int U,V,num[2];
int send_message(int n,int i,int Pi){
    //printf(" %i %i\n",i,Pi);
    i++,Pi++;
    if(i==2){
        depth[1]=1;
        U=V=1;
        num[0]=num[1]=0;
        for(int j=0;j<=lg;j++) par[1][j]=0;
    }
    E[i].pb(Pi);E[Pi].pb(i);
    depth[i]=depth[Pi]+1;
    par[i][0]=Pi;
    for(int j=1;j<=lg;j++) par[i][j]=par[par[i][j-1]][j-1];
    if(Dist(U,V)<Dist(i,V)) U=i;
    else if(Dist(U,V)<Dist(U,i)) V=i;
    //printf("%i: %i %i\n",i-1,U-1,V-1);
    //printf(" * %i %i\n",num[0],num[1]);
    //printf("%i %i: %i %i\n",i,Pi,U,V);
    if(i<=n-K) return 0;
    if(num[0]<lg&&num[1]<lg){
        if(i==U){
            num[0]=lg;
            return 3;
            /*int bit=V>>num[1]&1;
            num[1]++;
            return 3-bit;*/
        }
        if(i==V){
            num[1]=lg;
            return 4;
        }
        if(num[0]<lg){
            int bit=U>>num[0]&1;
            num[0]++;
            return 1-bit;
        }
    }
    else if(num[0]<lg&&num[1]>=lg){
        if(i==U){
            num[0]=lg;
            return 2;
        }
        if(i==V){
            num[1]=lg;
            int bit=U>>num[0]&1;
            num[0]++;
            return 4-bit;
        }
        if(num[0]<lg){
            int bit=U>>num[0]&1;
            num[0]++;
            return 1-bit;
        }
    }
    else if(num[0]>=lg&&num[1]<lg){
        if(i==U){
            num[0]=lg;
            int bit=V>>num[1]&1;
            num[1]++;
            return 4-bit;
        }
        if(i==V){
            num[1]=lg;
            return 2;
        }
        if(num[1]<lg){
            int bit=V>>num[1]&1;
            num[1]++;
            return 1-bit;
        }
    }
    else{
        if(i==U){
            num[0]=lg;
            return 3;
        }
        if(i==V){
            num[1]=lg;
            return 4;
        }
        return 0;
    }
    return 0;
}

pair<int,int>longest_path(vector<int>S){
    int n=S.size();
    int U=-1,V=-1;
    int num[2]={0};
    for(int i=n-K;i<n;i++){
        if(num[0]<lg&&num[1]<lg){
            if(S[i]==3){
                num[0]=lg;
                U=i;
            }
            else if(S[i]==2){
                num[0]=lg;
                U=i;
                V+=1<<num[1];
                num[1]++;
            }
            else if(S[i]==4){
                num[1]=lg;
                V=i;
            }
            else{
                if(num[0]<lg){
                    if(S[i]==0) U+=1<<num[0];
                    num[0]++;
                }
                /*else if(num[1]<lg){
                    if(S[i]==2) V+=1<<num[1];
                    num[1]++;
                }*/
            }
            //printf("{%i %i}\n",U,V);
        }
        else if(num[0]<lg&&num[1]>=lg){
            if(S[i]==2){
                U=i;
                num[0]=lg;
            }
            else if(S[i]>2){
                V=i;
                int bit=4-S[i];
                if(bit) U+=1<<num[0];
                num[0]++;
            }
            else{
                if(S[i]==0) U+=1<<num[0];
                num[0]++;
            }
        }
        else if(num[0]>=lg&&num[1]<lg){
            if(S[i]==2){
                V=i;
                num[1]=lg;
            }
            else if(S[i]>2){
                U=i;
                int bit=4-S[i];
                if(bit) V+=1<<num[1];
                num[1]++;
            }
            else{
                if(S[i]==0) V+=1<<num[1];
                num[1]++;
            }
        }
        else{
            if(S[i]==3){
                U=i;
                num[0]=lg;
            }
            else if(S[i]==4){
                V=i;
                num[1]=lg;
            }
        }
        //printf("- %i: %i %i %i %i\n",i,U,V,num[0],num[1]);
    }
    return make_pair(U,V);
}

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