Submission #519182

#TimeUsernameProblemLanguageResultExecution timeMemory
519182MOUF_MAHMALATTorrent (COI16_torrent)C++14
100 / 100
646 ms27712 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef int ll; ll n,a,b,op,x,y,dp[300009],pp[300009],ans; vector<vector<ll> >v; vector<ll>bin; inline void dfs(ll d,ll p) { pp[d]=p; for(auto&z:v[d]) if(z!=p) dfs(z,d); } inline void best(ll d,ll p) { dp[d]=0; vector<ll>o; for(auto&z:v[d]) { if(z==p||(d==x&&z==y)||(d==y&&z==x)) continue; best(z,d); o.push_back(dp[z]); } sort(all(o),greater<ll>()); for(ll i=0; i<o.size(); i++) dp[d]=max(dp[d],o[i]+i+1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>a>>b; v.resize(n+1); for(ll i=1; i<n; i++) { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } dfs(a,0); x=b; while(x) { bin.push_back(x); x=pp[x]; } reverse(all(bin)); x=bin[0],y=bin[1]; best(a,0),best(b,0); ans=max(dp[a],dp[b]); ll l=0,r=bin.size()-1,m; while(r-l>1) { m=(l+r)>>1; x=bin[m]; y=bin[m+1]; best(a,0); best(b,0); op=max(dp[a],dp[b]); if(ans<op) r=m; else l=m,ans=op; } r=l+1,l=0; while(r-l>1) { m=(l+r)>>1; x=bin[m-1]; y=bin[m]; best(a,0); best(b,0); op=max(dp[a],dp[b]); if(ans<op) l=m; else r=m,ans=op; } cout<<ans; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'void best(ll, ll)':
torrent.cpp:29:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(ll i=0; i<o.size(); i++)
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...