제출 #79828

#제출 시각아이디문제언어결과실행 시간메모리
79828PajarajaHard route (IZhO17_road)C++17
52 / 100
2063 ms166896 KiB
#include <bits/stdc++.h> #define MAXN 500007 using namespace std; vector<int> g[MAXN]; int b,mb,u,v; long long pot,cnt,d[MAXN],k[MAXN],ds[2][MAXN]; void dfsD(int s,int f,int di) { d[s]=di; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1); } void dfsd(int s,int f,int ka,int di) { ds[ka][s]=di; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1); } int dfsp(int s,int f) { int mx=0; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) mx=max(mx,dfsp(g[s][i],s)); d[s]=mx+1; return d[s]; } void calc(int s,int f,long long mx,long long du) { if(s!=f && g[s].size()==1) { if(s!=mb && du*mx==pot) cnt++; if(s!=mb && du*mx>pot) {pot=du*mx; cnt=1;} return; } int mxi=0; long long mx1=0,mx2=0; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;} for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]); calc(g[s][mxi],s,max(mx,mx2),du+1); for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1); } void dfs(int s,int f,long long du,int ka) { if(s==v || s==u) {d[s]=-MAXN; return;} if(g[s].size()==1 && s!=f) {k[s]=1; d[s]=1; return;} for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,du+1,ka); int mxi=0; long long mx1=0,mx2=0; k[s]=0; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;} for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]]; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]); d[s]=mx1+1; long long tc=0; if(mx1==mx2) { tc=k[s]*k[s]; for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]]; tc/=2; } else { for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]]; tc*=k[s]; } if(mx2==0 || (ka==1 && ds[0][s]==ds[1][s])) return; if((mx1+mx2)*du>pot) {pot=(mx1+mx2)*du; cnt=0;} if((mx1+mx2)*du==pot) cnt+=tc; } int main() { int n; u=1; v=1; scanf("%d",&n); for(int i=0;i<n-1;i++) { int t1,t2; scanf("%d%d",&t1,&t2); g[t1].push_back(t2); g[t2].push_back(t1); } dfsD(1,1,0); for(int i=1;i<=n;i++) if(d[i]>d[u]) u=i; dfsD(u,u,0); for(int i=1;i<=n;i++) if(d[i]>d[v]) v=i; dfsd(u,u,0,0); dfsd(v,v,1,0); dfsp(u,u); calc(u,u,0,0); mb=u; dfsp(v,v); calc(v,v,0,0); dfs(g[u][0],u,1,0); dfs(g[v][0],v,1,1); printf("%lld %lld",pot,cnt); }

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

road.cpp: In function 'void dfsD(int, int, int)':
road.cpp:10: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) dfsD(g[s][i],s,di+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'void dfsd(int, int, int, int)':
road.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) dfsD(g[s][i],s,di+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'int dfsp(int, int)':
road.cpp:20: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) mx=max(mx,dfsp(g[s][i],s));
              ~^~~~~~~~~~~~
road.cpp: In function 'void calc(int, int, long long int, long long int)':
road.cpp:34: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) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
              ~^~~~~~~~~~~~
road.cpp:35: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) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
              ~^~~~~~~~~~~~
road.cpp:37: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 && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'void dfs(int, int, long long int, int)':
road.cpp:43: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) dfs(g[s][i],s,du+1,ka);
              ~^~~~~~~~~~~~
road.cpp:47: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) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
              ~^~~~~~~~~~~~
road.cpp:48: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) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]];
              ~^~~~~~~~~~~~
road.cpp:49: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) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
              ~^~~~~~~~~~~~
road.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]];
               ~^~~~~~~~~~~~
road.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]];
               ~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
road.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...