oj.uz

Submission #764487

# Submission time Handle Problem Language Result Execution time Memory
764487 2023-06-23T12:57:07 Z safaricola Torrent (COI16_torrent) C++17
100 / 100
 456 ms 29760 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7328 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 25848 KB Output is correct
2 Correct 395 ms 27792 KB Output is correct
3 Correct 411 ms 29348 KB Output is correct
4 Correct 406 ms 28024 KB Output is correct
5 Correct 456 ms 25180 KB Output is correct
6 Correct 374 ms 25308 KB Output is correct
7 Correct 383 ms 29760 KB Output is correct