제출 #1360586

#제출 시각아이디문제언어결과실행 시간메모리
1360586jumpTorrent (COI16_torrent)C++20
100 / 100
1865 ms29172 KiB
#include <bits/stdc++.h>
#define int long long

int n,a,b;
std::vector<int> adj[300100];
std::vector<int> path;
int time(int curr,int parr,int ignore){
  std::vector<int> tot;
  for(auto to:adj[curr]){
    if(to==parr||to==ignore)continue;
    tot.push_back(time(to,curr,ignore));
  }
  std::sort(tot.rbegin(),tot.rend());
  int max = 0;
  for(int i=0;i<tot.size();i++){
    max=std::max(tot[i]+i+1,max);
  }
  return max;
}
bool solve(int req){
  int l=0,r=path.size()-1;
  while(l<r){
    int mid = (l+r+1)/2;
    if(mid==0||time(a,a,path[mid])<=req){
      l=mid;
    }
    else{
      r=mid-1;
    }
  }
  if(l==0)return false;
  return time(b,b,path[l-1])<=req;
}
bool findPath(int curr,int par){
  if(curr==b){
    path.push_back(curr);
    return true;
  }
  for(auto to:adj[curr]){
    if(to==par)continue;
    if(findPath(to,curr)){
      path.push_back(curr);
      return true;
    }
  }
  return false;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> a >> b;
  for(int i=0;i<n-1;i++){
    int in1,in2;
    std::cin >> in1 >> in2;
    adj[in1].push_back(in2);
    adj[in2].push_back(in1);
  }
  findPath(a,a);
  std::reverse(path.begin(),path.end());
  int l=1,r=n;
  while(l<r){
    int mid = (l+r)/2;
    if(solve(mid)){
      r=mid;
    }
    else{
      l=mid+1;
    }
  }
  std::cout << r;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…