Submission #1258314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258314		medmdg	Migrations (IOI25_migrations)	C++20	30 / 100	29 ms	1004 KiB

migrations

#include "migrations.h"
using namespace std;
vector<vector<int>> Tree;
int n;
vector<int> depth;
void init(){
  Tree.clear();
  Tree.resize(n);
  depth.clear();
  depth.resize(n);
  depth[0]=0;
}
int ans=0;
int perAns=-1;
int send_message(int N, int i, int Pi) {
  n=N;
  if(i==1){
    init();
  }
  Tree[Pi].push_back(i);
  depth[i]=depth[Pi]+1;
  if(depth[i]>depth[ans])ans=i;
  if(i<n-11)return 0;
  if(perAns==-1)perAns=ans;
  if(i==n-3){
    if(ans<n-11)return 1;
    int t=n-3-ans;
    if(ans==i)return 0;
    if(t>=3)return 4;
    return t+1;
  }
  if(i==n-2){
    if(ans<n-11)return 1;
    int t=n-3-ans;
    if(ans==i)return 0;
    if(t<=3)return 1;
    if(t>=6)return 4;
    t-=3;
    return t+1;
  }
  if(i==n-1){
    if(ans<n-11)return 1;
    int t=n-3-ans;
    if(ans==i)return 0;
    if(t<=3)return 1;
    t-=6;
    return t+1;
  }
  int re=perAns%4;
  perAns/=4;
  return re;
}

pair<int, int> longest_path(vector<int> S) {
  n=S.size();
  if(S.back()==0)return {0,n-1};
  if(S[n-2]==0)return {0,n-2};
  if(S[n-3]==0)return {0,n-3};
  if(S[n-3]==1){
    int ans=0;
    for(int i=n-4;i>=n-11;i--){
      ans*=4;
      ans+=S[i];
    }
    return {0,ans};
  }
  int ans=n-3;
  ans-=S[n-3]-1;
  ans-=S[n-2]-1;
  ans-=S[n-1]-1;
  return {0,ans};
}

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