Submission #719873

#	Time	Username	Problem	Language	Result	Execution time	Memory
719873		Ahmed57	Torrent (COI16_torrent)	C++14	100 / 100	820 ms	26388 KiB

torrent

#include <bits/stdc++.h>

using namespace std;
int par[300001];
vector<int> adj[300001];
void dfs(int i,int pr){
    par[i]= pr;
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
    }
}
int vis[300001];
long long calc(int i,int pr){
    if(vis[i]==1)return 0;
    vector<int> v;
    for(auto j:adj[i]){
        if(vis[j]||j==pr)continue;
        v.push_back(calc(j,i));
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int ma = 0;
    for(int j = 0;j<v.size();j++){
        ma = max(ma,v[j]+j+1);
    }
    return ma;
}
long long a,b,n;
bool can(long long mid){
    memset(vis,0,sizeof vis);
    int cur = b;
    int ti = 0;
    while(cur!=0){
        int ne = calc(cur,par[cur]);
        if(ne+ti<=mid){
            vis[cur] = 1;
            cur = par[cur];
            ti++;
        }else break;
    }
    if(calc(a,0)<=mid)return 1;
    else return 0;
}
signed main(){
    cin>>n>>a>>b;
    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(a,0);
    long long l = 1 , r = 1e9 , ans = 0;
    while(l<=r){
        long long mid = (l+r)/2;
        if(can(mid))r = mid-1,ans = mid;
        else l = mid+1;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

torrent.cpp: In function 'long long int calc(int, int)':
torrent.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j = 0;j<v.size();j++){
      |                   ~^~~~~~~~~

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