제출 #868545

#제출 시각아이디문제언어결과실행 시간메모리
868545LeVanThucHard route (IZhO17_road)C++17
100 / 100
624 ms139888 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,const T2 &y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,const T2 &y) { if(x>y) { x=y; return 1; } return 0; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.INP","r",stdin); freopen("output.OUT","w",stdout); #else #endif } const ll N=5e5+10,M=1e9+7; ll par[N],in[N],cnt[N],n,ans,res; vector<ll> gr[N]; void dfs(ll u) { cnt[u]=1; in[u]=1; for(auto v:gr[u]) { if(v==par[u]) continue; par[v]=u; dfs(v); if(maximize(in[u],in[v]+1)) cnt[u]=0; if(in[u]==in[v]+1) { cnt[u]+=cnt[v]; } } } void dp(ll u,ll out,ll outc) { vector<pll> vt; if(u!=1) vt.emplace_back(out,outc); for(auto v:gr[u]) { if(v==par[u]) continue; vt.emplace_back(in[v],cnt[v]); } sort(vt.begin(),vt.end(),greater<pll>()); if(vt.size()>=3&&(vt[0].fi*(vt[1].fi+vt[2].fi))>=res) { ll curres=(vt[0].fi*(vt[1].fi+vt[2].fi)),curcnt=0; ll ba=0; for(auto v:vt) { if(v.fi==vt[2].fi) ba+=v.se; } if(vt[1].fi==vt[2].fi) { ll cnt=0; for(auto [x,num]:vt) { if(x==vt[1].fi) { curcnt+=cnt*num; cnt+=num; } } } else if(vt[0].fi==vt[1].fi) { curcnt=(vt[0].se+vt[1].se)*ba; } else { curcnt=vt[1].se*ba; } if(maximize(res,curres)) ans=0; ans+=curcnt; } ll mx1=vt[0].fi,mx1c=0,mx2=0,mx2c=1; if(vt.size()>=2) mx2=vt[1].fi,mx2c=0; for(auto [v,num]:vt) { if(v==mx1) mx1c+=num; if(v==mx2) mx2c+=num; } for(auto v:gr[u]) { if(v==par[u]) continue; if(in[v]==mx1) { if(cnt[v]==mx1c) dp(v,mx2+1,mx2c); else dp(v,mx1+1,mx1c-cnt[v]); } else dp(v,mx1+1,mx1c); } } int main() { online(); cin>>n; ans=1; for(int i=1; i<n; i++) { ll u,v; cin>>u>>v; gr[u].push_back(v); gr[v].push_back(u); } ll flag=1,cnt=0; for(int i=1;i<=n;i++) { if(gr[i].size()>2) flag=0; if(gr[i].size()==1) cnt++; } // if(flag&&cnt==2) // { // cout<<"0 1"; // return 0; // } dfs(1); dp(1,0,1); cout<<res<<' '<<ans<<'\n'; }

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

road.cpp: In function 'int main()':
road.cpp:134:8: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
  134 |     ll flag=1,cnt=0;
      |        ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...