Submission #708864

#TimeUsernameProblemLanguageResultExecution timeMemory
708864alvingogoDesignated Cities (JOI19_designated_cities)C++14
100 / 100
519 ms70760 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue #define int long long using namespace std; struct no{ vector<pair<int,pair<int,int> > > ch; int sum=0; int sum2=0; pair<int,int> dp={0,-1},dp2={0,-1}; }; int n; int zz=0; vector<no> v; vector<int> ans; void dfs(int r,int f){ for(auto h:v[r].ch){ if(h.fs!=f){ dfs(h.fs,r); v[r].sum+=v[h.fs].sum+h.sc.sc; } } } void dfs2(int r,int f,int z=0){ v[r].sum+=z; ans[1]=max(ans[1],v[r].sum); for(auto h:v[r].ch){ if(h.fs!=f){ dfs2(h.fs,r,h.sc.fs+v[r].sum-v[h.fs].sum-h.sc.sc); } } } void calc1(){ dfs(0,0); ans[1]=max(ans[1],v[0].sum); dfs2(0,0); } vector<int> t; void dfs3(int r,int f){ vector<int> g; for(auto h:v[r].ch){ if(h.fs!=f){ dfs3(h.fs,r); g.push_back(v[h.fs].sum2+h.sc.fs); } } sort(g.begin(),g.end(),greater<int>()); if(!g.size()){ return; } if(g.size()>1){ for(int i=1;i<g.size();i++){ t.push_back(g[i]); } } v[r].sum2=g[0]; } pair<int,pair<int,int> > dfs4(int r,int f){ pair<int,pair<int,int> > ret={0,{-1,-1}}; auto c=v[r].dp,d=v[r].dp2; for(auto h:v[r].ch){ if(h.fs!=f){ ret=max(ret,dfs4(h.fs,r)); ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}}); ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}}); v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc}); v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc}); } } reverse(v[r].ch.begin(),v[r].ch.end()); v[r].dp=c; v[r].dp2=d; for(auto h:v[r].ch){ if(h.fs!=f){ ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}}); ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}}); v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc}); v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc}); } } return ret; } void calc2(){ for(int i=0;i<n;i++){ if(v[i].ch.size()==1){ v[i].dp.fs=v[i].sum; v[i].dp.sc=i; v[i].dp2.sc=i; } } auto h=dfs4(0,0); for(int i=0;i<n;i++){ if(i==h.sc.fs || i==h.sc.sc){ for(int j=0;j<n;j++){ v[j].sum2=0; } t.clear(); dfs3(i,i); t.push_back(v[i].sum2); sort(t.begin(),t.end(),greater<int>()); int nw=v[i].sum; while(t.size()<=n){ t.push_back(0); } for(int j=2;j<=n;j++){ nw+=t[j-2]; ans[j]=max(ans[j],nw); } } } assert(ans[2]==h.fs); } signed main(){ AquA; cin >> n; v.resize(n); for(int i=1;i<n;i++){ int a,b; cin >> a >> b; a--; b--; int c,d; cin >> c >> d; zz+=c+d; v[a].ch.push_back({b,{c,d}}); v[b].ch.push_back({a,{d,c}}); } ans.resize(n+1); calc1(); calc2(); int q; cin >> q; for(int i=0;i<q;i++){ int a; cin >> a; cout << zz-ans[a] << "\n"; } return 0; }

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs3(long long int, long long int)':
designated_cities.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=1;i<g.size();i++){
      |                     ~^~~~~~~~~
designated_cities.cpp: In function 'void calc2()':
designated_cities.cpp:106:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  106 |             while(t.size()<=n){
      |                   ~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...