Submission #507176

#TimeUsernameProblemLanguageResultExecution timeMemory
507176ponkungTorrent (COI16_torrent)C++14
0 / 100
176 ms29148 KiB
#include<bits/stdc++.h> using namespace std; int n,a,b,u_i,v_i,dp[300005],p[300005],lv[300005],ans=-1,mx,it,hsh[300005],dis1[300005],dis2[300005],u; vector<int> v[300005],g; queue<int> q; void dfs(int u) { if(v[u].size()==1&&v[u][0]==p[u]) { //printf("node=%d\n",u); return; } for(int i=0;i<v[u].size();i++) { if(p[u]!=v[u][i]) { lv[v[u][i]]=lv[u]+1; p[v[u][i]]=u; dfs(v[u][i]); } } for(int i=0;i<v[u].size();i++) { if(v[u][i]!=p[u]) { g.push_back(dp[v[u][i]]); } } //printf("node=%d\n",u); sort(g.begin(),g.end()); for(int i=0;i<g.size();i++) { dp[u]=max(dp[u],g[i]+(int)g.size()-i); //printf("%d ",g[i]); } //printf("\n"); g.clear(); } int lca(int x,int y) { while(1) { //printf("%d %d %d %d\n",x,y,lv[x],lv[y]); if(lv[x]==lv[y]) { if(x==y) { return x; }else { x=p[x]; } }else if(lv[x]>=lv[y]) { x=p[x]; }else { y=p[y]; } } } int compute(int x,int y) { mx=-1; it=0; while(1) { //printf("node=%d\n",x); //printf("it=%d\n",it); mx=max(mx,it); for(int i=0;i<v[x].size();i++) { if(v[x][i]!=p[x]&&hsh[v[x][i]]==0) { g.push_back(dp[v[x][i]]); } } sort(g.begin(),g.end()); for(int i=0;i<g.size();i++) { mx=max(mx,it+g[i]+(int)g.size()-i); //printf("%d ",g[i]); } //printf("\n"); //printf("max=%d\n",mx); g.clear(); if(x==y) { break; } hsh[x]=1; x=p[x]; it=min(dis1[x],dis2[x]); } return mx; } int main() { scanf("%d%d%d",&n,&a,&b); for(int i=1;i<n;i++) { scanf("%d%d",&u_i,&v_i); v[u_i].push_back(v_i); v[v_i].push_back(u_i); } dfs(1); /*for(int i=1;i<=n;i++) { printf("%d\n",dp[i]); }*/ /*for(int i=1;i<=n;i++) { printf("%d\n",lv[i]); }*/ memset(dis1,-1,sizeof dis1); memset(dis2,-1,sizeof dis2); dis1[a]=0; dis2[b]=0; q.push(a); while(!q.empty()) { u=q.front(); q.pop(); for(int i=0;i<v[u].size();i++) { if(dis1[v[u][i]]==-1) { dis1[v[u][i]]=dis1[u]+1; q.push(v[u][i]); } } } q.push(b); while(!q.empty()) { u=q.front(); q.pop(); for(int i=0;i<v[u].size();i++) { if(dis2[v[u][i]]==-1) { dis2[v[u][i]]=dis2[u]+1; q.push(v[u][i]); } } } /*for(int i=1;i<=n;i++) { printf("%d %d\n",dis1[i],dis2[i]); }*/ ans=max(ans,compute(a,lca(a,b))); ans=max(ans,compute(b,lca(a,b))); ans=max(ans,compute(lca(a,b),1)); printf("%d\n",ans); }

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int)':
torrent.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
torrent.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
torrent.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<g.size();i++)
      |                 ~^~~~~~~~~
torrent.cpp: In function 'int compute(int, int)':
torrent.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
torrent.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<g.size();i++)
      |                     ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
torrent.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
torrent.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d%d",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d%d",&u_i,&v_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...