Submission #1287086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287086		eri16	Migrations (IOI25_migrations)	C++20	0 / 100	35 ms	976 KiB

migrations

#include <bits/stdc++.h>
using namespace std;

vector <int> v[10005];

int ans;

int T[10005];
int K[10005];
int J[10005];


pair<int,int> bfs(int node, int mx){
    
    int n=mx; vector<int> dist(n,-1);
    queue<int> q; dist[node]=0; q.push(node); int f=node;
    
    while (!q.empty()){
    int t=q.front();
    q.pop();
    for (int i=0; i<v[t].size(); i++) {
        int to=v[t][i];
        if (dist[to]==-1){
        dist[to]=dist[t]+1;q.push(to);
        if (dist[to]>dist[f])f=to;
    }}}
    
    return {f,dist[f]};
}

int div5[6]={1,5,25,125,625,3125};
int mod5[6]={5,25,125,625,3125,15625};

//[A],A,A,A,A,A,X,X,X,X,X,X,[B],B,Y,Y,[C],Z,T

int send_message(int N, int i, int Pi){
    if (i<9981){
        v[i].push_back(Pi);
        v[Pi].push_back(i);
        return 0;
    }
    
    else if(i>=9981 && i<=9986){
        int j=9986-i;
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p1,p2,p3,p4;
        p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
        J[i]=p2.second;
        
        if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
        else{
            p3=bfs(T[i-1],i+1);
            p4=bfs(K[i-1],i+1);
            
            if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
            else{T[i]=p4.first;K[i]=K[i-1];}            
        }
        
        return (T[9981]%mod5[j]/div5[j]);
    }
    else if(i>=9987 && i<=9992){
        int j=9992-i;
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p1,p2,p3,p4;
        p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
        J[i]=p2.second;
        
        if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
        else{
            p3=bfs(T[i-1],i+1);
            p4=bfs(K[i-1],i+1);
            
            if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
            else{T[i]=p4.first;K[i]=K[i-1];}            
        }
        
        return (K[9981]%mod5[j]/div5[j]);
    }

    else if(i==9993){
        
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p1,p2,p3,p4;
        p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
        J[i]=p2.second;
        
        if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
        else{
            p3=bfs(T[i-1],i+1);
            p4=bfs(K[i-1],i+1);
            
            if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
            else{T[i]=p4.first;K[i]=K[i-1];}            
        }
        
        ans=0;
        
        if (T[9993]<=9981){ans=0;}
        else{ans=T[9993]-9981;}
            
        return(ans/5);
    }
    else if(i==9994){
        
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p1,p2,p3,p4;
        p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
        J[i]=p2.second;
        
        if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
        else{
            p3=bfs(T[i-1],i+1);
            p4=bfs(K[i-1],i+1);
            
            if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
            else{T[i]=p4.first;K[i]=K[i-1];}            
        }

        return(ans%5);
    }
else if(i==9995){
        
    v[i].push_back(Pi);v[Pi].push_back(i);
    pair <int,int> p1,p2,p3,p4;
    p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
    J[i]=p2.second;
        
    if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
    else{
        p3=bfs(T[i-1],i+1);
        p4=bfs(K[i-1],i+1);
            
        if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
        else{T[i]=p4.first;K[i]=K[i-1];}            
    }
        
    ans=0;
        
    if (K[9993]<=9981){ans=0;}
    else{ans=K[9993]-9981;}
               
    return(ans/5);
    }
else if(i==9996){
        
    v[i].push_back(Pi);v[Pi].push_back(i);
    pair <int,int> p1,p2,p3,p4;
    p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
    J[i]=p2.second;
        
    if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
    else{
        p3=bfs(T[i-1],i+1);
        p4=bfs(K[i-1],i+1);
            
        if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
        else{T[i]=p4.first;K[i]=K[i-1];}            
    }

    return(ans%5);
}
else if(i==9997){
    v[i].push_back(Pi);v[Pi].push_back(i);
    pair <int,int> p1,p2,p3,p4;
    p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
    J[i]=p2.second;
        
    if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
    else{
        p3=bfs(T[i-1],i+1);
        p4=bfs(K[i-1],i+1);
            
        if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
        else{T[i]=p4.first;K[i]=K[i-1];}            
    }      
    ans=0;
    if (T[9997]<=9993){ans=0;}
    else{ans=T[9997]-9993;}
    return ans;
}    
else if(i==9998){
    v[i].push_back(Pi);v[Pi].push_back(i);
    pair <int,int> p1,p2,p3,p4;
    p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
    J[i]=p2.second;
        
    if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
    else{
        p3=bfs(T[i-1],i+1);
        p4=bfs(K[i-1],i+1);
            
        if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
        else{T[i]=p4.first;K[i]=K[i-1];}            
    }      
    ans=0;
    if (K[9997]<=9993){ans=0;}
    else{ans=K[9997]-9993;}
    return ans;
}
else{
    v[i].push_back(Pi);v[Pi].push_back(i);
    pair <int,int> p1,p2,p3,p4;
    p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
    J[i]=p2.second;
        
    if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
        
    else{
        p3=bfs(T[i-1],i+1);
        p4=bfs(K[i-1],i+1);
            
        if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
        else{T[i]=p4.first;K[i]=K[i-1];}            
    }  

    if (K[9999]<=9997 && T[9999]<=9997){
        return 0;
    }
    else if(T[9999]=9998){
        return 1;
    }
    else if(T[9999]=9999){
        return 2;
    }
    else if(K[9999]=9999){
        return 3;
    }
    else{
        return 4;
    }
    
    
}
}

long long intPow(long long base, long long exp1) {
    long long result = 1;
    while (exp1--) result *= base;
    return result;
}

std::pair<int,int> longest_path(std::vector<int> S){
    int pos_ans_x=0;
    int pos_ans_y=0;
    
    for (int i=9981; i<9987; i++){
        pos_ans_x+=S[i]*intPow(5,9986-i);
    }
    for (int i=9987; i<9993; i++){
        pos_ans_x+=S[i]*intPow(5,9992-i);
    }    
    
    int nm_x=0;
    int nm_y=0;
    
    nm_x=S[9993]*5+S[9994];
    nm_y=S[9995]*5+S[9996];   
    
    if (nm_x!=0){
        pos_ans_x=9981+nm_x;
    }
    if (nm_y!=0){
        pos_ans_y=9981+nm_y;
    } 
    
    nm_x=S[9997];
    nm_y=S[9998];  
    
    if (nm_x!=0){
        pos_ans_x=9993+nm_x;
    }
    if (nm_y!=0){
        pos_ans_y=9993+nm_y;
    }     
    
    if (S[9999]==4){
        pos_ans_x=9998;
        pos_ans_y=9999;
    }
    if (S[9999]==3){
        pos_ans_y=9999;
    }
    if (S[9999]==2){
        pos_ans_x=9999;
    }
    if (S[9999]==1){
        pos_ans_x=9998;
    }    
    return {pos_ans_x,pos_ans_y};
}

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