Submission #477990

#	Time	Username	Problem	Language	Result	Execution time	Memory
477990		tar_palantir	Torrent (COI16_torrent)	C++17	100 / 100	514 ms	32796 KiB

torrent

#include<bits/stdc++.h>
#define int long long
#define task "copydata"

using namespace std;
using ii=pair<int,int>;

const int mn=3e5+11,inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
 
template<typename t>
bool ckmax(t& target,const t& source){
    return target<source ? target=source,1 : 0;
}
template<typename t>
bool ckmin(t& target,const t& source){
    return target>source ? target=source,1 : 0;
}

int n,a,b;
int p[mn];
vector<int>adj[mn];

void prevs(int u,int pre){
    for(int v:adj[u])if(v!=pre)
        p[v]=u,prevs(v,u);
}

int dp[mn];

int calc(int u,int pre,int barr){
    vector<int>cur;
    for(int v:adj[u])if(v!=pre && v!=barr)
        cur.emplace_back(calc(v,u,barr));
    
    sort(cur.begin(),cur.end(),greater<int>());
    for(int i=0;i<cur.size();i++)
        ckmax(dp[u],i+1+cur[i]);

    return dp[u];
}

ii eval(int k){
    ii res;
    memset(dp,0,sizeof(dp));
    res.first=calc(b,-1,p[k]);

    memset(dp,0,sizeof(dp));
    res.second=calc(a,-1,k);
    return res;
}
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    #ifdef _TPR_
        freopen("t.inp","r",stdin);
        freopen("t.out","w",stdout);
    #endif
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=1,u,v;i<n;i++){
        scanf("%lld%lld",&u,&v);
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    prevs(a,-1);

    vector<int>tmp;int z=b;
    while(z)tmp.emplace_back(z),z=p[z];

    int l=0,r=(int)tmp.size()-2,ans=-1;
    ii res(inf,inf);
    while(l<=r){
        int mid=l+r>>1;
        ii cur=eval(tmp[mid]);
        if(cur.first<=cur.second)res=cur,ans=mid,l=mid+1;
        else r=mid-1;
    }

    int true_res=max(res.first,res.second);
    if(ans+1<tmp.size()){
        ii cur=eval(tmp[ans+1]);
        ckmin(true_res,max(cur.first,cur.second));
    }
    cout<<true_res;
}

Compilation message (stderr)

torrent.cpp: In function 'long long int calc(long long int, long long int, long long int)':
torrent.cpp:37: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]
   37 |     for(int i=0;i<cur.size();i++)
      |                 ~^~~~~~~~~~~
torrent.cpp: In function 'int32_t main()':
torrent.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid=l+r>>1;
      |                 ~^~
torrent.cpp:80:13: 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]
   80 |     if(ans+1<tmp.size()){
      |        ~~~~~^~~~~~~~~~~
torrent.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%lld%lld%lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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