Submission #698859

#	Time	Username	Problem	Language	Result	Execution time	Memory
698859		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	316 ms	31288 KiB

torrent

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100;
int n,f[N],A,B,fa[N];
vector<int>ss,v[N],d;
void solve(int x,int y,int t)
{
    for(int i:v[x])
        if(i!=y&&i!=t)solve(i,x,t);
    ss.clear();f[x]=0;
    for(int i:v[x])
        if(i!=y&&i!=t)ss.push_back(f[i]);
    sort(ss.begin(),ss.end());
    reverse(ss.begin(),ss.end());
    for(int i=0;i<ss.size();i++)
        f[x]=max(f[x],i+1+ss[i]);
}
void dfs(int x)
{
    for(int i:v[x])
        if(i!=fa[x])fa[i]=x,dfs(i);
}
signed main()
{
    scanf("%lld%lld%lld",&n,&A,&B);
    for(int i=1,x,y;i<n;i++)
        scanf("%lld%lld",&x,&y),
        v[x].push_back(y),v[y].push_back(x);
    dfs(A);
    int now=B;
    while(now!=A)
        d.push_back(now),now=fa[now];
    d.push_back(A);
    reverse(d.begin(),d.end());
    int l=0,r=d.size()-2,mid,ans=1e18;
    while(l<=r)
    {
        mid=(l+r)>>1;
        solve(A,0,d[mid+1]),solve(B,0,d[mid]);
        // cout<<d[mid+1]<<' '<<d[mid]<<endl;
        // cout<<"ANS="<<
        ans=min(ans,max(f[A],f[B]));
        if(f[A]>f[B])r=mid-1;
        else l=mid+1;
    }   
    printf("%lld\n",ans);
}

Compilation message (stderr)

torrent.cpp: In function 'void solve(long long int, long long int, long long int)':
torrent.cpp:16:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0;i<ss.size();i++)
      |                 ~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld%lld%lld",&n,&A,&B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%lld%lld",&x,&y),
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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