Submission #1255104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255104		tosivanmak	Migrations (IOI25_migrations)	C++20	72.89 / 100	40 ms	1464 KiB

migrations

#include "migrations.h"
#include<bits/stdc++.h>
using namespace std;
#define ll int

ll dep[10005];
ll maxdep=0; ll nd;
vector<ll>btsmol,btbig;
bool vis[10005];
vector<ll>adj[10005];
vector<ll> conv(ll x){
    vector<ll>v;
    for(int i=0;i<=13;i++){
        if(x&(1LL<<i)){
            v.push_back(1);
        }
        else{
            v.push_back(0);
        }
    }
    return v;
}
// N-i<=19
// 10000 9981
// 9981 to 9999 19 information
void dfs(ll s){
    vis[s]=1;
    for(auto& u: adj[s]){
        if(!vis[u]){
            dep[u]=dep[s]+1;
            dfs(u);
        }
    }
}
pair<ll,ll>pr;
ll oris,orib;
int send_message(int N, int id, int Pi) {
   
   if(N-id>28){adj[id].push_back(Pi); adj[Pi].push_back(id);return 0;}
   if(N-id==28){
       dfs(0);
       ll maxi=0; ll nd;
       for(int i=0;i<id;i++){
           if(dep[i]>maxi){
               maxi=dep[i]; nd=i;
           }
       }
       for(int i=0;i<id;i++)dep[i]=0,vis[i]=0;
       dfs(nd);
       ll store=nd;
       maxi=0; nd=0;
       for(int i=0;i<id;i++){
           if(dep[i]>maxi){
               maxi=dep[i]; nd=i;
           }
       }
       pr={min(store,nd),max(store,nd)};
       btsmol=conv(pr.first); btbig=conv(pr.second);
       oris=pr.first,orib=pr.second;
       for(int i=0;i<id;i++){
           vis[i]=0; dep[i]=0;
       }
   }
   adj[id].push_back(Pi); adj[Pi].push_back(id);
   dfs(pr.first); ll val1=dep[id]; ll comp1=dep[pr.second];
   for(int i=0;i<=id;i++){
       vis[i]=0; dep[i]=0;
   }
   dfs(pr.second); ll val2=dep[id]; ll comp2=dep[pr.first];
   for(int i=0;i<=id;i++)vis[i]=0,dep[i]=0;
   if(pr.first>=9972&&pr.second>=9972){
       if(val1>comp1){
           // replace big
           pr.second=id;
           return 2;
       }
       else if(val2>comp2){
           // replace small
           pr.first=pr.second; pr.second=id;
           return 1;
       }
       else{
           // not replace
           return 0;
       }
   }
   else if(pr.first==oris){
       if(val1>comp1){
           // replace big
           pr.second=id;
           if(id>=9972&&id<=9985){
               // sending small
               return 2+btsmol[id-9972];
           }
           else{
               // sending big
               return 4;
           }
       }
       else if(val2>comp2){
           // replace small
           pr.first=pr.second; pr.second=id;
           if(id>=9972&&id<=9985){
               // sending small
               return 4;
           }
           else{
               // sending big
               return 2+btbig[id-9986];
           }
       }
       else{
           // not replace
           if(id>=9972&&id<=9985){
               // sending small
               return btsmol[id-9972];
           }
           else{
               // sending big
               return btbig[id-9986];
           }
       }
   }
   else if(pr.first==orib&&pr.second>=9972){
       if(val1>comp1){
           // replace big
           pr.second=id;
           if(id>=9972&&id<=9985){
               // sending small
               return 4;
           }
           else{
               // sending big
               return 2+btbig[id-9986];
           }
       }
       else if(val2>comp2){
           // replace small
           pr.first=pr.second; pr.second=id;
           if(id>=9972&&id<=9985){
               // sending small
               return 2;
           }
           else{
               // sending big
               return 4;
           }
       }
       else{
           // not replace
           if(id>=9972&&id<=9985){
               // sending small
               return 0;
           }
           else{
               // sending big
               return btbig[id-9986];
           }
       }
   }
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int smol=0,lar=0;
    pr.first=-2; pr.second=-1;
    for(int id=9972;id<=9999;id++){
        if(pr.first>=9972&&pr.second>=9972){
        if(S[id]==2){
            // replace big
            pr.second=id;
        }
        else if(S[id]==1){
            // replace small
            pr.first=pr.second; pr.second=id;
        }
        else{
            // not replace
        }
    }
    else if(pr.first==-2){
            // replace big
            
            if(id>=9972&&id<=9985){
                // sending small
                if(S[id]>=2&&S[id]<=3){
                    pr.second=id; smol+=(S[id]-2)*(1LL<<(id-9972));
                }
                else if(S[id]==4){
                    pr.first=pr.second; pr.second=id;
                }
                else{
                    smol+=(S[id])*(1LL<<(id-9972));
                }
            }
            else{
                // sending big
                if(S[id]>=2&&S[id]<=3){
                    pr.first=pr.second; pr.second=id;
                    lar+=(S[id]-2)*(1LL<<(id-9986));
                }
                else if(S[id]==4){
                    pr.second=id; 
                }
                else{
                    lar+=(S[id])*(1LL<<(id-9986));
                }
            }
    }
    else if(pr.first==-1&&pr.second>=9972){
            // replace big
            if(id>=9972&&id<=9985){
                // sending small
                if(S[id]==4){pr.second=id;}
                else if(S[id]==2){pr.first=pr.second; pr.second=id;}
                else{}
            }
            else{
                // sending big
                if(S[id]>=2&&S[id]<=3){
                    pr.second=id;
                    lar+=(S[id]-2)*(1LL<<(id-9986));
                }
                else if(S[id]==4){
                    pr.first=pr.second; pr.second=id;
                }
                else{
                    lar+=(S[id])*(1LL<<(id-9986));
                }
            }
        
    }
   }
   if(pr.first==-2)pr.first=smol;
   if(pr.first==-1)pr.first=lar;
   if(pr.second==-1)pr.second=lar;
   return {pr.first,pr.second};
}

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:161:1: warning: control reaches end of non-void function [-Wreturn-type]
  161 | }
      | ^

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