제출 #1325090

#제출 시각아이디문제언어결과실행 시간메모리
1325090SonicMLTorrent (COI16_torrent)C++20
31 / 100
2094 ms21976 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int const INF = 1e9+7;

int const NMAX = 3e5;

int n;

vector <int> g[1 + NMAX];

int dist;
vector <int> path;

bool buildPath(int node, int parent, int target) {
  if(node == target) {
    path.push_back(node);
    return true;
  }
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(to != parent) {
      if(buildPath(to, node, target)) {
        path.push_back(node);
        return true;
      }
    }
  }
  return false;
}

int dp[1 + NMAX];

void computeDp(int node, int parent, int border) {
  dp[node] = 0; 
  //cerr << "  " << node << "/\n";
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(to != parent && to != border) {
      computeDp(to, node, border);  
    }
  }
  vector <int> aux;
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(to != parent && to != border) {
      aux.push_back(dp[to]);
    }
  }
  if(aux.size() > 0) {
    sort(aux.begin(), aux.end());
    int add = aux.size();
    for(int i = 0;i < aux.size();i++) {
      dp[node] = max(dp[node], aux[i]+add);
      add--;
    }
  }
  //cerr << "  " << node << " : " << dp[node] << "\\\n";
}

int solve(int root, int borderDist) {
  int border; 
  if(root == path[0]) {
    border = path[borderDist];
  }else {
    border = path[path.size()-borderDist-1];
  }
  //cerr << root << " :\n";
  computeDp(root, root, border);
  return dp[root];
}

int cautbinLimit(int from, int to, int root, int limit) {
  if(from >= to) {
    if(solve(root, from) <= limit) {
      return from;
    }else {
      return -INF;
    }
  }else {
    int mid = (from + to + 1) / 2;
    if(solve(root, mid) <= limit) {
      return cautbinLimit(mid, to, root, limit);
    }else {
      return cautbinLimit(from, mid-1, root, limit);
    }
  }
}

int cautbin(int from, int to, int sourceA, int sourceB) {
  if(from >= to) {
    return from;
  }else {
    int mid = (from + to) / 2;
    int limitA = cautbinLimit(1, dist, sourceA, mid);
    int limitB = cautbinLimit(1, dist, sourceB, mid);
    if(limitA + limitB >= dist+1) {
      return cautbin(from, mid, sourceA, sourceB);
    }else {
      return cautbin(mid+1, to, sourceA, sourceB);
    }
  }
}

int main() {

  int sourceA, sourceB;
  cin >> n >> sourceA >> sourceB;
  for(int i = 1;i < n;i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  buildPath(sourceB, sourceB, sourceA);
  dist = path.size()-1;
  cout << cautbin(1, n, sourceA, sourceB);
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...