Submission #520795

#	Time	Username	Problem	Language	Result	Execution time	Memory
520795		krit3379	Torrent (COI16_torrent)	C++17	100 / 100	382 ms	27816 KiB

torrent

#include<bits/stdc++.h>
using namespace std;
#define N 300005

int id[N],sz,ans=2e9;
vector<int> g[N];
bitset<N> in;

bool find_path(int s,int f,int e){
    if(s==e){
        id[s]=++sz;
        return in[s]=true;
    }
    for(auto x:g[s]){
        if(x==f)continue;
        if(find_path(x,s,e)){
            id[s]=++sz;
            return in[s]=true;
        }
    }
    return in[s];
}

int dfs1(int s,int f,int lim){
    int ma=0;
    vector<int> v;
    for(auto x:g[s]){
        if(x==f||id[x]>lim)continue;
        v.push_back(dfs1(x,s,lim));
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
    return ma;
}

int dfs2(int s,int f,int lim){
    int ma=0;
    vector<int> v;
    for(auto x:g[s]){
        if(x==f||(id[x]&&id[x]<=lim))continue;
        v.push_back(dfs2(x,s,lim));
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
    return ma;
}

int main(){
    int n,i,s1,s2,a,b,l,r,mid,val1,val2;
    scanf("%d %d %d",&n,&s1,&s2);
    for(i=1;i<n;i++){
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    find_path(s2,0,s1);
    l=1,r=sz-1;
    while(l<=r){
        mid=(l+r)/2;
        val1=dfs1(s1,0,mid);
        val2=dfs2(s2,0,mid);
        ans=min(ans,max(val1,val2));
        if(val1>val2)r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs1(int, int, int)':
torrent.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
      |                 ~^~~~~~~~~
torrent.cpp: In function 'int dfs2(int, int, int)':
torrent.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<v.size();i++)ma=max(ma,v[i]+i+1);
      |                 ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d %d",&n,&s1,&s2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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