oj.uz

Submission #523899

# Submission time Handle Problem Language Result Execution time Memory
523899 2022-02-08T11:38:27 Z Fake4Fun Torrent (COI16_torrent) C++14
100 / 100
 380 ms 22536 KB 
//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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 5 ms 7360 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 19292 KB Output is correct
2 Correct 341 ms 20780 KB Output is correct
3 Correct 340 ms 22280 KB Output is correct
4 Correct 380 ms 21596 KB Output is correct
5 Correct 361 ms 18752 KB Output is correct
6 Correct 317 ms 19540 KB Output is correct
7 Correct 314 ms 22536 KB Output is correct