oj.uz

Submission #474540

# Submission time Handle Problem Language Result Execution time Memory
474540 2021-09-19T02:27:21 Z tar_palantir Torrent (COI16_torrent) C++17
100 / 100
 509 ms 25256 KB 
#include<bits/stdc++.h>
using namespace std;
using ii=pair<int,int>;

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

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],0);
    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;
}

Compilation message

torrent.cpp: In function 'int calc(int, int, int)':
torrent.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<eval.size();i++)
      |                 ~^~~~~~~~~~~~
torrent.cpp: In function 'int32_t main()':
torrent.cpp:73:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid=(l+r>>1);
      |                  ~^~
torrent.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     if(opt+2<tmp.size()){
      |        ~~~~~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Correct 6 ms 8524 KB Output is correct
3 Correct 6 ms 8524 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 21592 KB Output is correct
2 Correct 488 ms 23216 KB Output is correct
3 Correct 506 ms 24900 KB Output is correct
4 Correct 509 ms 24396 KB Output is correct
5 Correct 459 ms 21188 KB Output is correct
6 Correct 418 ms 21832 KB Output is correct
7 Correct 403 ms 25256 KB Output is correct