제출 #1257734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257734		erering	Migrations (IOI25_migrations)	C++20	79.12 / 100	38 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>=9979 && i<9993){
   if(i==9979){
    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<=9985){
    if(e>di){
      ans={i,ans.second};
      di=e;
      return 4;
    }
    int shft=(i-9979)*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-9986)*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;
    return x;
   }
  }
  adj[i].pb(Pi);
  adj[Pi].pb(i);
  if(i>=9993){
    //  cout<<ans.first<<' '<<ans.second<<endl;
      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(e>0){
          ans.first=i;
          di=e;
          return 3;
      }
    lk=i-7; e=0;
    dfs(i,-1);
    if(e>0){
      ans={i,i-7};
      di=e;
      return 4;
    }

    if(ans.second!=i-7){
      lk=ans.second; e=0;
      dfs(i-7,-1);
      if(e>0){
        ans.first=i-7;
        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=9979;i<9993;i++){
    if(i==9986){
      p=1;
      fl=0;
    }
    if(S[i]==4){
      if(i<=9985)x=i;
      else y=i;
      fl=1;
    }
    if(fl)continue;
    if(S[i]==1 || S[i]==3){
      if(i<=9985)x+=p;
      else y+=p;
    }
    p*=2;
    if(S[i]==2 || S[i]==3){
      if(i<=9985)x+=p;
      else y+=p;
    }
    p*=2;
  }
 // cout<<x<<' '<<y<<endl;
  for(int i=9993;i<=9999;i++){
    if(S[i]==0)continue;
    if(S[i]==4){
      x=i; y=i-7;
      continue;
    }
    if(S[i]==1)x=i-7;
    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: 49.1152 / 70