제출 #1287011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287011		eri16	Migrations (IOI25_migrations)	C++20	0 / 100	31 ms	1084 KiB

migrations

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

vector <int> v[10005];

int ans;

int T[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};

int send_message(int N, int i, int Pi){
    if (i<9991){
        v[i].push_back(Pi);
        v[Pi].push_back(i);
        return 0;
    }
    
    else if(i>=9991 && i<=9996){
        int j=9996-i;
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p;p=bfs(0,i+1);
        T[i]=p.first;J[i]=p.second;
        
        return (T[9991]%mod5[j]/div5[j]);
    }

    else if(i==9997){
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p;p=bfs(0,9998);
        T[9997]=p.first;J[9997]=p.second;ans=0;
        
        for (int j=9991; j<=9997; j++)if(J[j]>=J[9996]){ans=j-9991;break;}
            
        return(ans/5);
    }
    else if(i==9998){
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p;p=bfs(0,N-1);
        T[9998]=p.first;J[9998]=p.second;        
        return(ans%5);
    }
    else{
        v[i].push_back(Pi);v[Pi].push_back(i);
        pair <int,int> p;p=bfs(0,N);
        T[9999]=p.first;J[9999]=p.second;    
        if (J[9997]>=J[9999]){ans=0;}
        else if (J[9998]>=J[9999]){ans=1;}
        else{ans=2;}
        return (ans);
    }
}

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=0;
    //return {0,S.size()-2};
    for (int i=10000-9; i<10000-3; i++){
        pos_ans+=S[i]*intPow(5,10000-4-i);
    }
    if (S[10000-3]==1){
        pos_ans=10000-3;
        if (S[10000-2]==0){pos_ans=10000-4;}   
    }
    else if(S[10000-2]!=0){
        pos_ans=10000-9+S[10000-2];
    }
    if (S[10000-1]==2){
        pos_ans=10000-1;
//        return {-S[10000-1],-S[10000-2]};
    }
    if (S[10000-1]==1){
        pos_ans=10000-2;        
    }
    return {0,pos_ans};
}

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