Submission #523889

#	Time	Username	Problem	Language	Result	Execution time	Memory
523889		Fake4Fun	Torrent (COI16_torrent)	C++14	69 / 100	406 ms	29700 KiB

torrent

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+5;
int n,a,b;
vector<int> adj[N];
int ord[N];
void DFS(int pre,int u){
    if(u==b) return;
    for(auto i:adj[u]) if(i!=pre){
        DFS(u,i);
        if(ord[i]) ord[u]=ord[i]+1;
    }
}
int Cal(int pre,int u,int L,int R){
    vector<int> tmp;
    for(auto i:adj[u]){
        if(i==pre||(L<=ord[i]&&ord[i]<=R)) continue;
        tmp.push_back(Cal(u,i,L,R));
    }
    if(tmp.empty()) return 0;
    sort(begin(tmp),end(tmp),greater<int>());
    int ma=0;
    for(int i=0;i<(int)tmp.size();i++) ma=max(ma,tmp[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);
    }
    ord[b]=1;
    DFS(0,a);
    int l=1, r=ord[a]-1, ans=N;
    while(l<=r){
        int mid=(l+r)>>1;
        int v1=Cal(0,a,1,mid), v2=Cal(0,b,mid+1,ord[a]);
        ans=min(ans,max(v1,v2));
        if(v1>v2) r=--mid;
        else l=++mid;
    }
    cout<<ans;
    return 0;
}

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