Submission #1310095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310095		exoworldgd	Migrations (IOI25_migrations)	C++20	100 / 100	37 ms	1216 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;
const int D=14,MX=10005;
int jp[MX][D],dep[MX],ct[10],wl[15],n,sz0,sz1,szw;
pair<int,int>diam,pv,cd0[MX],cd1[MX],cp[15];
int szcp;
const pair<int,int>pt[5][5]={{{0,4},{0,5},{0,6},{0,8},{8,4}},{{0,7},{1,7},{1,4},{1,8},{8,7}},{{1,5},{1,6},{2,6},{2,8},{8,6}},{{2,4},{2,5},{3,5},{3,8},{8,5}},{{3,4},{3,6},{3,7},{2,7},{0,0}}};
int lca(int a,int b){
    dep[a]<dep[b]?swap(a,b),0:0;
    for(int d=D-1;d>=0;d--)(dep[a]-dep[b])&(1<<d)?(a=jp[a][d]):0;
    for(int d=D-1;d>=0;d--)jp[a][d]!=jp[b][d]?(a=jp[a][d],b=jp[b][d]):0;
    return jp[a][0];
}
int ds(int a,int b){return dep[a]+dep[b]-2*dep[lca(a,b)];}
void ex(pair<int,int>*v,int&sv,int pr,int r){
    while(sv%pr)v[sv++]=v[sv-1];
    int ns=sv/pr,st=ns*r;
    for(int i=0;i<ns;i++)v[i]=v[st+i];
    sv=ns;
}
int ix(pair<int,int>*v,int&sv,int g,int pr){
    while(sv%pr)v[sv++]=v[sv-1];
    int i=0;
    while(v[i].first!=g)i++;
    int r=i*pr/sv;
    ex(v,sv,pr,r);
    return r;
}
void ic(int N){ct[0]=N-173,ct[1]=N-33,ct[2]=N-13,ct[3]=N-7,ct[4]=N-5,ct[5]=N-3,ct[6]=N;}
bool cm(pair<int,int>a,pair<int,int>b){return a.first==b.first||a.first==b.second||a.second==b.first||a.second==b.second;}
void aa(int nv){
    pair<int,int>tmp[15];
    int st=0;
    for(int i=0;i<szcp;i++)tmp[st++]=cp[i];
    for(int i=0;i<szcp;i++)tmp[st++]={cp[i].first,nv},tmp[st++]={cp[i].second,nv};
    sort(tmp,tmp+st),szcp=0;
    for(int i=0;i<st;i++)if(!i||tmp[i]!=tmp[i-1])cp[szcp++]=tmp[i];
}
void vo(){
    sort(cp,cp+szcp);
    do{
        bool ok=1;
        for(int i=0;i+1<szcp;i+=2)if(!cm(cp[i],cp[i+1])){ok=0;break;}
        if(ok)return;
    }while(next_permutation(cp,cp+szcp));
}
pair<int,int>pe(pair<int,int>t){return{wl[t.first],wl[t.second]};}
bool eq(pair<int,int>a,pair<int,int>b){return(a.first==b.first&&a.second==b.second)||(a.first==b.second&&a.second==b.first);}
int c2(int x){return x*(x+1)/2;}
int send_message(int N,int i,int Pi){
    if(i==1){
        n=N,memset(jp,0,sizeof jp),memset(dep,0,sizeof dep),sz0=1,sz1=1,cd0[0]={0,0},cd1[0]={0,0},diam={0,0};
        ic(N);
    }
    jp[i][0]=Pi,dep[i]=dep[Pi]+1;
    for(int d=1;d<D;d++)jp[i][d]=jp[jp[i][d-1]][d-1];
    for(int j=0;j<2;j++)if(ds(i,j?diam.second:diam.first)>ds(diam.first,diam.second)){j?diam.first=i:diam.second=i;break;}
    int ci=0,mg=0;
    while(ct[ci+1]<=i)ci++;
    if(ci>0&&ct[ci]==i)for(int j=ct[ci-1]+1;j<ct[ci];j++)cd0[sz0++]={j,0},cd1[sz1++]={j,0};
    if(i>=ct[5]){
        if(i==ct[5]){
            szw=0;
            for(int j=0;j<sz0;j++)wl[szw++]=cd0[j].first;
            for(int j=0;j<sz1;j++)wl[szw++]=cd1[j].first;
            wl[szw++]=i;
            while(1){
                bool f=0;
                for(int k=0;k<5;k++)if(diam==pe(pt[mg][k]))f=1;
                if(f)break;
                mg++;
            }
            szcp=0;
            for(int k=0;k<5;k++)if(pt[mg][k].first||pt[mg][k].second)cp[szcp++]=pt[mg][k];
        }else if(i==ct[5]+1){
            wl[szw++]=i;
            aa(9);
            vo();
            while(szcp<10)cp[szcp]=cp[szcp-1],szcp++;
            int r=0;
            while(!eq(diam,pe(cp[r])))r++;
            mg=r/2;
            ex(cp,szcp,5,mg);
        }else{
            wl[szw++]=i;
            aa(10);
            while(!eq(diam,pe(cp[mg])))mg++;
        }
    }else if(i>=ct[0]){
        if(i==ct[ci]){
            cd0[sz0++]={i,0},cd1[sz1++]={i,0};
            const int sp=ct[ci+1]-ct[ci],nc=4*sp+1;
            int te=0;
            if(!ci){
                int sc=1;
                while(c2(sc+1)<=nc)++sc;
                diam.first<diam.second?swap(diam.first,diam.second),0:0,te=c2(ix(cd0,sz0,diam.first,sc))+ix(cd1,sz1,diam.second,sc);
            }else{
                int sc=sqrt(nc);
                te=sc*ix(cd0,sz0,diam.first,sc)+ix(cd1,sz1,diam.second,sc);
            }
            te==4*sp?pv={-1,-1}:pv={i+te/4,1+te%4};
        }
        if(i==pv.first)mg=pv.second;
    }else cd0[sz0++]={i,0},cd1[sz1++]={i,0};
    return mg;
}
pair<int,int>longest_path(vector<int>S){
    memset(dep,0,sizeof dep),memset(jp,0,sizeof jp);
    sz0=0,sz1=0,diam={0,0};
    int N=S.size();
    ic(N);
    for(int i=0;i<N;i++){
        int ci=0;
        while(ct[ci+1]<=i)ci++;
        if(ci>0&&ct[ci]==i){
            int sp=ct[ci]-ct[ci-1],nc=4*sp+1,sc=0,te=0;
            ci==1?0:sc=sqrt(nc);
            if(ci==1)while(c2(sc+1)<=nc)sc++;
            pv==make_pair(-1,-1)?te=4*sp:te=(pv.first-ct[ci-1])*4+(pv.second-1);
            pair<int,int>ix{};
            if(ci==1){
                while(c2(ix.first+1)<=te)++ix.first;
                ix.second=te-c2(ix.first);
            }else ix={te/sc,te%sc};
            ex(cd0,sz0,sc,ix.first),ex(cd1,sz1,sc,ix.second);
            for(int j=ct[ci-1]+1;j<ct[ci];j++)cd0[sz0++]={j,0},cd1[sz1++]={j,0};
        }
        int mg=S[i];
        if(i>=ct[5]){
            if(i==ct[5]){
                szw=0;
                for(int j=0;j<sz0;j++)wl[szw++]=cd0[j].first;
                for(int j=0;j<sz1;j++)wl[szw++]=cd1[j].first;
                wl[szw++]=i;
                szcp=0;
                for(int k=0;k<5;k++)if(pt[mg][k].first||pt[mg][k].second)cp[szcp++]=pt[mg][k];
            }else if(i==ct[5]+1){
                wl[szw++]=i;
                aa(9);
                vo();
                while(szcp<10)cp[szcp]=cp[szcp-1],szcp++;
                ex(cp,szcp,5,mg);
            }else{
                wl[szw++]=i;
                aa(10);
                return pe(cp[mg]);
            }
        }else if(i>=ct[0]){
            if(i==ct[ci])pv={-1,-1},cd0[sz0++]={i,0},cd1[sz1++]={i,0};
            mg?pv={i,mg},0:0;
        }else cd0[sz0++]={i,0},cd1[sz1++]={i,0};
        if(i==N-1)return{cd0[0].first,cd1[0].first};
    }
    return{0,0};
}

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