제출 #1255822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255822		erering	Migrations (IOI25_migrations)	C++20	72.89 / 100	43 ms	1204 KiB

migrations

#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
#define pb push_back
pair<int,int> ans={-1,-1},mx={-1,-1};
int di,lk=-1;
vector<int> adj[10005];
int e=0,rr=-1;
void dfs(int node,int par,int dist=0){
  if(lk==-1 && mx.first<dist)mx={dist,node};
  if(lk!=-1 && node==lk && dist>di)e=dist;
  for(auto i:adj[node]){
    if(i==par)continue;
    dfs(i,node,dist+1);
  }
}
int send_message(int N, int i, int Pi) {
  if(i>=9972 && i<9986){
   if(i==9972){
    dfs(0,-1);
    int x=mx.second;
    rr=x;
    mx={-1,-1};
    dfs(x,-1);
    ans={x,mx.second};
    di=mx.first;
   rr=-1;
   }
   adj[i].pb(Pi);
   adj[Pi].pb(i);
   e=0; lk=ans.second;
   dfs(i,-1);
   if(i<=9978){
    if(e>di){
      ans={i,ans.second};
      di=e;
      return 4;
    }
    int shft=(i-9972)*2;
    bool t1=0,t2=0;
    if(((ans.first>>shft)&1))t1=1;
    shft++;
    if(((ans.first>>shft)&1))t2=1;
    int x=t1;
    if(t2)x+=2;
    //cout<<shft<<' '<<ans.first<<' '<<x<<endl;
    return x;
   }
   else{
     e=0; lk=ans.first;
     dfs(i,-1);
    if(e>di){
      ans={ans.first,i};
      di=e;
      return 4;
    }
    int shft=(i-9979)*2;
    bool t1=0,t2=0;
    if(((ans.second>>shft)&1))t1=1;
    shft++;
    if(((ans.second>>shft)&1))t2=1;
    int x=t1;
    if(t2)x+=2;
    //cout<<shft<<"E "<<x<<' '<<ans.second<<endl;
    return x;
   }
  }
 // if(i==1)cout<<i<<' '<<Pi<<'s'<<endl;
  adj[i].pb(Pi);
  adj[Pi].pb(i);
  if(i>=9986){
    mx={-1,-1};
    lk=i-14; e=0;
    dfs(i,-1);
    if(e>0){
      ans={i,i-14};
      di=e;
      return 4;
    }
    lk=ans.first; e=0;
    dfs(i,-1); //we have replaced second dude
    if(e>0){
      ans.second=i;
      di=e;
      return 2;
    }
    lk=ans.second; e=0;
    dfs(i,-1); //we have replaced first dude
    //if(i==9998)
    if(e>0){
      ans.first=i;
      di=e;
      return 3;
    }

    if(ans.first!=i-14 && i-14<=9978){
      lk=ans.first; e=0;
      dfs(i-14,-1); //we have replaced second dude
      if(e>0){
        ans.second=i-14;
        di=e;
        return 1;
      }
    }
    else if(ans.second!=i-14 && i-14>9978){
      lk=ans.second; e=0;
      dfs(i-14,-1);
      if(e>0){
        ans.first=i-14;
        di=e;
        return 1;
      }
    }
  }
  return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
  int x=0,y=0,p=1;
  bool fl=0;
  for(int i=9972;i<9986;i++){
    if(i==9979){
      p=1;
      fl=0;
    }
    if(S[i]==4){
      if(i<=9978)x=i;
      else y=i;
      fl=1;
    }
    if(fl)continue;
    if(S[i]==1 || S[i]==3){
      if(i<=9978)x+=p;
      else y+=p;
    }
    p*=2;
    if(S[i]==2 || S[i]==3){
      if(i<=9978)x+=p;
      else y+=p;
    }
    p*=2;
  }
  for(int i=9986;i<=9999;i++){
    if(S[i]==0)continue;
    if(S[i]==4){
      x=i; y=i-14;
      continue;
    }
    if(S[i]==1){
if(i-14<=9977)y=i-14;
else x=i-14;
}
    if(S[i]==2)y=i;
    if(S[i]==3)x=i;
  }
  return {x,y};
}

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