제출 #755556

#제출 시각아이디문제언어결과실행 시간메모리
755556bgnbvnbvTorrent (COI16_torrent)C++14
100 / 100
609 ms49484 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=int; const ll maxN=3e5+10; const ll mod=1e9+7; ll dp[maxN]; vector<ll>g[maxN]; ll sz,vc[maxN]; void dfs1(ll u,ll p,ll cam) { dp[u]=0; for(auto v:g[u]) { if(v!=p&&v!=cam) { dfs1(v,u,cam); } } sz=0; for(auto v:g[u]) { if(v!=p&&v!=cam) { sz++; vc[sz]=dp[v]; } } sort(vc+1,vc+sz+1,greater<ll>()); for(int i=1;i<=sz;i++) dp[u]=max(dp[u],vc[i]+i); } ll P[maxN][19],h[maxN]; ll anc(ll u,ll k) { for(int i=18;i>=1;i--) if(k>>i&1) u=P[u][i]; return u; } void dfs(ll u,ll p) { P[u][0]=p; for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1]; for(int v:g[u]) { if(v!=p) { h[v]=h[u]+1; dfs(v,u); } } } ll b,a; ll cal(ll mid) { ll x=anc(b,mid); ll y=P[x][0]; dfs1(a,a,x); dfs1(b,b,y); return max(dp[a],dp[b]); } ll n; void solve() { cin >> n >> a >> b; for(int i=1;i<n;i++) { ll u,v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(a,a); ll dis=h[b]-h[a]; ll low=1,high=dis-1; while(low<=high) { ll mid=low+high>>1; cal(mid); if(dp[b]>dp[a]) high=mid-1; else low=mid+1; } ll ans=cal(high); //cout << high<<'\n'; low=0,high=dis-2; while(low<=high) { ll mid=low+high>>1; cal(mid); if(dp[b]>=dp[a]) high=mid-1; else low=mid+1; } ans=min(ans,cal(low)); cout << ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

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

torrent.cpp: In function 'void solve()':
torrent.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         ll mid=low+high>>1;
      |                ~~~^~~~~
torrent.cpp:94:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ll mid=low+high>>1;
      |                ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...