Submission #1310077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310077		exoworldgd	Migrations (IOI25_migrations)	C++20	0 / 100	190 ms	748 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<int>p,dep,c0,c1,csz={182,25,6,1,1,1,1,1};
int n,e1,e2,cst,cid;
int getd(int v){
    if(dep[v]==-1)dep[v]=(v==0)?0:getd(p[v])+1;
    return dep[v];
}
int lca(int u,int v){
    while(u!=v)getd(u)>getd(v)?u=p[u]:v=p[v];
    return u;
}
int dist(int u,int v){
    int l=lca(u,v);
    return getd(u)+getd(v)-2*getd(l);
}
int send_message(int N,int i,int Pi){
    if(i==1){
        n=N,p.assign(N,0),dep.assign(N,-1),e1=0,e2=0,cst=1,cid=0;
        c0.clear(),c1.clear();
        for(int j=0;j<N;j++)c0.push_back(j),c1.push_back(j);
    }
    p[i]=Pi,dep[i]=-1;
    int d1=dist(i,e1),d2=dist(i,e2),cd=dist(e1,e2),nd=max({cd,d1,d2});
    nd>cd?(d1>=d2?e2=i:e1=i,0):0;
    c0.push_back(i),c1.push_back(i);
    if(i==cst+csz[cid]-1||i==N-1){
        int s0=c0.size(),s1=c1.size(),B=csz[cid],msg=0;
        if(!cid){
            int k=floor(sqrt(4.0*B+1)),ns0=(s0+k-1)/k,b0=-1,b1=-1;
            for(int j=0;j<k;j++){
                for(int x=j*ns0;x<min((j+1)*ns0,s0);x++)c0[x]==e1?b0=j:0;
                for(int x=j*((s1+B-1)/k);x<min((j+1)*((s1+B-1)/k),s1);x++)c1[x]==e2?b1=j:0;
            }
            msg=b0*k+b1+1;
            vector<int>nc0,nc1;
            for(int j=b0*ns0;j<min((b0+1)*ns0,s0);j++)nc0.push_back(c0[j]);
            for(int j=b1*((s1+B-1)/k);j<min((b1+1)*((s1+B-1)/k),s1);j++)nc1.push_back(c1[j]);
            c0=nc0,c1=nc1;
        }else if(s0<=4&&s1<=4){
            int i0=-1,i1=-1;
            for(int j=0;j<s0;j++)c0[j]==e1?i0=j:0;
            for(int j=0;j<s1;j++)c1[j]==e2?i1=j:0;
            msg=i0*s1+i1+1;
            c0={e1},c1={e2};
        }else{
            int k=floor(sqrt(4.0*B+1)),ns=(s0+k-2)/k+1,b0=-1,b1=-1;
            for(int j=0;j<k;j++){
                for(int x=j*ns;x<min((j+1)*ns,s0);x++)c0[x]==e1?b0=j:0;
                for(int x=j*ns;x<min((j+1)*ns,s1);x++)c1[x]==e2?b1=j:0;
            }
            msg=b0*k+b1+1;
            vector<int>nc0,nc1;
            for(int j=b0*ns;j<min((b0+1)*ns,s0);j++)nc0.push_back(c0[j]);
            for(int j=b1*ns;j<min((b1+1)*ns,s1);j++)nc1.push_back(c1[j]);
            c0=nc0,c1=nc1;
        }
        cid++,cst=i+1;
        return msg;
    }
    return 0;
}
pair<int,int>longest_path(vector<int>S){
    int N=S.size();
    vector<int>c0,c1;
    for(int j=0;j<N;j++)c0.push_back(j),c1.push_back(j);
    int cid=0,cst=1;
    for(int i=1;i<N;i++){
        c0.push_back(i),c1.push_back(i);
        if(S[i]&&cid<8){
            int msg=S[i]-1,B=csz[cid],s0=c0.size(),s1=c1.size();
            if(cid==0){
                int k=floor(sqrt(4.0*B+1)),b0=msg/k,b1=msg%k,ns0=(s0+k-1)/k;
                vector<int>nc0,nc1;
                for(int j=b0*ns0;j<min((b0+1)*ns0,s0);j++)nc0.push_back(c0[j]);
                for(int j=b1*((s1+B-1)/k);j<min((b1+1)*((s1+B-1)/k),s1);j++)nc1.push_back(c1[j]);
                c0=nc0,c1=nc1;
            }else if(s0<=4&&s1<=4){
                int i0=msg/s1,i1=msg%s1;
                return{c0[i0],c1[i1]};
            }else{
                int k=floor(sqrt(4.0*B+1)),b0=msg/k,b1=msg%k,ns=(s0+k-2)/k+1;
                vector<int>nc0,nc1;
                for(int j=b0*ns;j<min((b0+1)*ns,s0);j++)nc0.push_back(c0[j]);
                for(int j=b1*ns;j<min((b1+1)*ns,s1);j++)nc1.push_back(c1[j]);
                c0=nc0,c1=nc1;
            }
            cid++,cst=i+1;
        }
    }
    return{c0[0],c1[0]};
}

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