제출 #474539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474539		tar_palantir	Torrent (COI16_torrent)	C++17	100 / 100	527 ms	29244 KiB

torrent

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ii=pair<int,int>;

const int mn=3e5+11,inf=0x3f3f3f3f3f3f3f3f;

template<typename t>
bool ckmin(t& target,const t& source){
    return target>source ? target=source,1 : 0;
}
template<typename t>
bool ckmax(t& target,const t& source){
    return target<source ? target=source,1 : 0;
}

int n,x,y;
vector<int>adj[mn];

int p[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){
    if(dp[u]!=-1)return dp[u];

    vector<int>eval;
    for(int v:adj[u])if(v!=pre && v!=barr)
        eval.emplace_back(calc(v,u,barr));

    sort(eval.begin(),eval.end(),greater<int>());
    for(int i=0;i<eval.size();i++)
        ckmax(dp[u],i+1+eval[i]);
    
    ckmax(dp[u],0LL);
    return dp[u];
}

vector<int>tmp;

ii eval(int k){
    memset(dp,-1,sizeof(dp));
    int ex=calc(x,-1,tmp[k+1]);
    memset(dp,-1,sizeof(dp));
    int ey=calc(y,-1,tmp[k]);
    return ii(ex,ey);
}
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    #ifdef _TPR_
        freopen("t.inp","r",stdin);
        freopen("t.out","w",stdout);
    #endif

    cin>>n>>x>>y;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    prevs(x,-1);

    int z=y;
    while(z)
        tmp.emplace_back(z),z=p[z];
    reverse(tmp.begin(),tmp.end());

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

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'long long int calc(long long int, long long int, long long int)':
torrent.cpp:35: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]
   35 |     for(int i=0;i<eval.size();i++)
      |                 ~^~~~~~~~~~~~
torrent.cpp: In function 'int32_t main()':
torrent.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         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(opt+2<tmp.size()){
      |        ~~~~~^~~~~~~~~~~

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