Submission #54679

#TimeUsernameProblemLanguageResultExecution timeMemory
54679PajarajaTorrent (COI16_torrent)C++17
100 / 100
1862 ms47636 KiB
#include <bits/stdc++.h> using namespace std; vector<int> g[300007],v; int n,a,b; bool ld,zb[300007]; void fr(int s,int f) { if(s==b) ld=true; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !ld) fr(g[s][i],s); if(ld) {v.push_back(s); return;} } int calc(int s,int f) { priority_queue<int> pq; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !zb[g[s][i]]) pq.push(calc(g[s][i],s)); int maxv=0,cnt=1; while(!pq.empty()) { maxv=max(maxv,pq.top()+cnt); pq.pop(); cnt++; } return maxv; } int val(int x) { zb[v[x+1]]=true; int v1=calc(a,0); zb[v[x+1]]=false; zb[v[x]]=true; int v2=calc(b,0); zb[v[x]]=false; return max(v1,v2); } int main() { scanf("%d%d%d",&n,&a,&b); for(int i=0;i<n-1;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } fr(a,0); int l=0,r=v.size()-2; reverse(v.begin(),v.end()); while(r-l>5) { int s1=(2*l+r)/3; int s2=(l+2*r)/3; int x=val(s1),y=val(s2); if(x>y) l=s1; else r=s2; } int minv=n+1; for(int i=l;i<=r;i++) minv=min(minv,val(i)); printf("%d",minv); }

Compilation message (stderr)

torrent.cpp: In function 'void fr(int, int)':
torrent.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !ld) fr(g[s][i],s);
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int calc(int, int)':
torrent.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !zb[g[s][i]]) pq.push(calc(g[s][i],s));
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...