Submission #1255064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255064		NemanjaSo2005	Migrations (IOI25_migrations)	C++20	56.23 / 100	37 ms	1208 KiB

migrations

#include "migrations.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e4+5;
int n=1e4-1;
vector<int> stablo[maxn];
int salji[maxn];
int dist[maxn];
void dfs(int gde,int pret,int d){
   dist[gde]=d;
   for(int x:stablo[gde])
      if(x!=pret)
         dfs(x,gde,d+1);
}
vector<int> cand;
int getdist(int a,int b){
   dfs(a,a,0);
   return dist[b];
}
int send_message(int N, int idx, int par) {
   if(idx<n-10){
      stablo[par].push_back(idx);
      stablo[idx].push_back(par);
      return 0;
   }
   if(idx==n-10){
      dfs(0,0,0);
      int d1=0;
      for(int i=0;i<idx;i++)
         if(dist[i]>dist[d1])
            d1=i;
      dfs(d1,d1,0);
      int d2=d1;
      for(int i=0;i<idx;i++)
         if(dist[i]>dist[d2])
            d2=i;

      cand.push_back(d1);
      cand.push_back(d2);

      for(int i=n-10;i<n-6;i++){
         salji[i]=d1%10;
         d1/=10;
      }
      for(int i=n-6;i<n-2;i++){
         salji[i]=d2%10;
         d2/=10;
      }
      stablo[par].push_back(idx);
      stablo[idx].push_back(par);
      return salji[idx];
   }
   if(idx>n-10 and idx<n-2){
      stablo[par].push_back(idx);
      stablo[idx].push_back(par);
      return salji[idx];
   }
   if(idx==n-2){
      for(int i=n-10;i<n-2;i++)
         cand.push_back(i);
      sort(cand.begin(),cand.end());
      int d=0,broj,cnt=0,a,b;
      for(int i=0;i<cand.size();i++)
         for(int j=i+1;j<cand.size();j++){
            cnt++;
            int dd=getdist(cand[i],cand[j]);
            if(dd>d){
               d=dd;
               a=cand[i];
               b=cand[j];
               broj=cnt;
            }
         }
      cand.clear();
      cand.push_back(a);
      cand.push_back(b);
      salji[idx]=broj%10;
      salji[idx+1]=broj/10;
      stablo[par].push_back(idx);
      stablo[idx].push_back(par);
      return salji[idx];
   }
   if(idx==n-1){
      stablo[par].push_back(idx);
      stablo[idx].push_back(par);
      return salji[idx];
   }
   stablo[par].push_back(idx);
   stablo[idx].push_back(par);

   for(int i=n-2;i<=n;i++)
      cand.push_back(i);
   sort(cand.begin(),cand.end());
   int d=0,broj,cnt=0;
   for(int i=0;i<cand.size();i++)
      for(int j=i+1;j<cand.size();j++){
         int dd=getdist(cand[i],cand[j]);
         if(dd>d){
            d=dd;
            broj=cnt;
         }
         cnt++;
      }
   return broj;
}

std::pair<int, int> longest_path(std::vector<int> S) {
   cand.clear();
   int a=0,b=0;
   for(int i=n-7;i>=n-10;i--){
      a=a*10+S[i];
   }
   for(int i=n-3;i>=n-6;i--)
      b=b*10+S[i];
   cand.push_back(a);
   cand.push_back(b);
   for(int i=n-10;i<=n-3;i++)
      cand.push_back(i);
   sort(cand.begin(),cand.end());
   int br=S[n-1]*10+S[n-2];
   for(int i=0;i<cand.size();i++)
      for(int j=i+1;j<cand.size();j++){
         br--;
         if(br==0){
            a=cand[i];
            b=cand[j];
         }
      }
   cand.clear();
   cand.push_back(a);
   cand.push_back(b);
   for(int i=n-2;i<=n;i++)
      cand.push_back(i);

   sort(cand.begin(),cand.end());
   br=S[n]+1;
   for(int i=0;i<cand.size();i++)
      for(int j=i+1;j<cand.size();j++){
         br--;
         if(br==0){
            a=cand[i];
            b=cand[j];
         }
      }
   return {a,b};
}

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