Submission #764487

#	Time	Username	Problem	Language	Result	Execution time	Memory
764487		safaricola	Torrent (COI16_torrent)	C++17	100 / 100	456 ms	29760 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1; i<=n; i++)
#define ii pair<int,int>
#define pb push_back
int n,a,b,A,B,dist[300010],getedge[300010],edgecnt,removed;
vector<ii> adj[300010];
bool edgesgen(int x, int p){
    if(x==B)return 1;
    for(auto [it,i]: adj[x])if(it!=p){
        dist[it]=dist[x]+1;
        if(edgesgen(it,x)){
            getedge[dist[it]]=i;
            edgecnt++;
            return 1;
        }
    }
    return 0;
}
int dfs(int x, int p){
    priority_queue<int> pq;
    for(auto [it,i] : adj[x])if(it!=p&&i!=removed){
        pq.push(dfs(it,x));
        //cout<<it<<' '<<pq.top()<<endl;
    }
    if(!pq.size())return 0;
    int ad=1,ret=0;
    while(pq.size()){
        ret=max(ret,pq.top()+ad);
        ad++;pq.pop();
    }
    return ret;
}
int main(){
    cin>>n>>A>>B;
    rep(i,n-1){
        cin>>a>>b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    edgesgen(A,-1);
    //rep(i,n)cout<<getedge[i]<<' ';
    //cout<<edgecnt;
    int s=0, e=edgecnt, mid;
    while(e-s>1){
        mid=(e+s)/2;
        removed=getedge[mid];
        int AA=dfs(A,-1);
        int BB=dfs(B,-1);
        //cout<<mid<<s<<' '<<e<<' '<<' '<<AA<<' '<<BB<<endl;
        if(AA>BB)e=mid;
        else s=mid;
    }
    removed=getedge[e];
    int AA=dfs(A,-1);
    int BB=dfs(B,-1);
    removed=getedge[s];
    int AAA=dfs(A,-1);
    int BBB=dfs(B,-1);
    cout<<min(max(AAA,BBB),max(AA,BB));
}
/*
6 2 1 
1 2
2 3
2 4
1 5
5 6

17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
*/

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