Submission #523899

#	Time	Username	Problem	Language	Result	Execution time	Memory
523899		Fake4Fun	Torrent (COI16_torrent)	C++14	100 / 100	380 ms	22536 KiB

torrent

//source: https://oj.uz/problem/view/COI16_torrent

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+5;
int n,a,b;
vector<int> adj[N],ror;
void DFS(int pre,int u){
    if(u==b) return;
    for(auto i:adj[u]) if(i!=pre){
        DFS(u,i);
        if(i==ror.back()) ror.push_back(u);
    }
}
int Cal(int pre,int u,int ban){
    vector<int> v;
    for(auto i:adj[u]){
        if(i==pre||i==ban) continue;
        v.push_back(Cal(u,i,ban));
    }
    if(v.empty()) return 0;
    sort(begin(v),end(v),greater<int>());
    int ma=0;
    for(int i=0;i<(int)v.size();i++) ma=max(ma,v[i]+i);
    return ma+1;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>a>>b;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ror.push_back(b);
    DFS(0,a);
    int l=0, r=ror.size(), ans=N;
    while(l<=r){
        int mid=(l+r)>>1;
        int v1=Cal(0,a,ror[mid]), v2=Cal(0,b,ror[mid+1]);
        ans=min(ans,max(v1,v2));
        if(v1>v2) l=++mid;
        else r=--mid;
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69