Submission #1258436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258436		medmdg	Migrations (IOI25_migrations)	C++20	30 / 100	35 ms	1560 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define Z 5
vector<vector<int>> Tree;
int n;
vector<int> depth;
int turnsLeft;
int stage;
int message;
void init(){
  Tree.clear();
  Tree.resize(n);
  depth.clear();
  depth.resize(n);
  depth[0]=0;
  message=0;
  stage=0;
  turnsLeft=n-31;
}
int cur;
pair<int,int> furthest(int ind,int par=-1){
    pair<int,int> ans= make_pair(0,ind);
    for(auto x:Tree[ind]){
        if(x==par)continue;
        pair<int,int> tmp= furthest(x,ind);
        if(tmp.first>ans.first){
            ans=tmp;
        }
    }
    ans.first++;
    return ans;
}
pair<int,int> diam(){
    int p1= furthest(0).second;
    int p2= furthest(p1).second;
    if(p1>p2)swap(p1,p2);
    return make_pair(p1,p2);
}
pair<int,int> lans;
void computeNext(){

    pair<int,int> ans=diam();
    if(stage==0){
        stage=1;
        message=ans.first*(10001)+ans.second;
        turnsLeft=12;
        lans=ans;
        return;
    }
    if(stage==1){
        int v1=cur-ans.first+1;
        if(ans.first==lans.first)v1=0;
        int v2=cur-ans.second+1;
        if(ans.second==lans.second||ans.first==lans.second)v2=0;
        lans=ans;
        stage=2;
        message=v1*(13)+v2;
        turnsLeft=4;
        return;
    }
    if(stage==2){
        int v1=cur-ans.first+1;
        if(ans.first==lans.first)v1=0;
        int v2=cur-ans.second+1;
        if(ans.second==lans.second||ans.first==lans.second)v2=0;
        stage=3;
        message=v1*(5)+v2;
        turnsLeft=2;
        lans=ans;
        return;
    }
    if(stage==3){
        int v1=cur-ans.first+1;
        if(ans.first==lans.first)v1=0;
        int v2=cur-ans.second+1;
        if(ans.second==lans.second||ans.first==lans.second)v2=0;
        stage=4;
        message=v1*(3)+v2;
        turnsLeft=1;
        lans=ans;
        return;
    }
    if(stage==4){
        turnsLeft=1;
        if(ans== make_pair(cur-1,cur)){
            message=5;
            lans=ans;
            return;
        }
        if(ans.second==cur){
            if(ans.first==lans.first) message=4;
            else message=3;
            lans=ans;
            return;
        }
        if(ans.second==cur-1){if( ans.first==lans.first)message=2;
        else message=1; lans=ans;return;}
        message=0;
        lans=ans;
        return;
    }
}
int send_message(int N, int i, int Pi) {
  n=N;
  cur=i;
  if(i==1){
    init();
  }
  Tree[Pi].push_back(i);
  Tree[i].push_back(Pi);
    if(turnsLeft==0){
        computeNext();
        //cout<<message<<endl;
    }
  if (turnsLeft){
        turnsLeft--;
        int res=message%Z;
        message/=Z;
        return res;
  }

}

pair<int, int> longest_path(vector<int> S) {
    n=S.size();
    message=0;
    for(int i=n-19;i>=n-30;i--){
      message*=Z;
      message+=S[i];
    }
    vector<int> ans={message%10001,message/10001};
    if(ans[0]>ans[1])swap(ans[0],ans[1]);
    message=0;
    for(int i=n-15;i>n-19;i--){
      message*=Z;
      message+=S[i];
    }
    pair<int,int> nans= make_pair(message/13,message%13);
    if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-18+1;
    if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-18+1;
    ans={nans.first,nans.second};
    message=0;
    for(int i=n-13;i>n-15;i--){
        message*=Z;
        message+=S[i];
    }
    nans= make_pair(message/5,message%5);
    if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-14+1;
    if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-14+1;
    ans={nans.first,nans.second};
    message=0;
    for(int i=n-12;i>n-13;i--){
        message*=Z;
        message+=S[i];
    }
    nans= make_pair(message/3,message%3);
    if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-12+1;
    if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-12+1;
    ans={nans.first,nans.second};
    for(int i=n-11;i<n;i++){
        message=S[i];
        if(message==5){
            ans={i-1,i};
            continue;
        }
        if(message==4){
            ans[1]=i;
            continue;
        }
        if(message==3){
            swap(ans[0],ans[1]);
            ans[1]=i;
            continue;
        }
        if(message==2){
            ans[1]=i-1;
            continue;
        }
        if(message==1){
            swap(ans[0],ans[1]);
            ans[1]=i-1;
            continue;
        }
    }
    return make_pair(ans[0],ans[1]);
}

Compilation message (stderr)

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

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