제출 #734336

#제출 시각아이디문제언어결과실행 시간메모리
734336bin9638도로 폐쇄 (APIO21_roads)C++17
7 / 100
2037 ms27708 KiB
#include <bits/stdc++.h> #ifndef SKY #include "roads.h" #endif // SKY using namespace std; #define N 100010 #define ll long long #define fs first #define sc second #define ii pair<ll,int> #define pb push_back #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("omit-frame-pointer") #pragma GCC optimize("unroll-loops") const ll MAX_VAL=2e14; int cnt,BLOCKS,k,n,ktr[N],spec[N]; vector<ii>g[N],edge[N]; ll tong,them,cost[N],dp[N][2]; vector<ll>sum[N]; vector<int>lis; struct nho { void build(int u,int p) { for(auto v:g[u]) if(v.sc!=p) { build(v.sc,u); cost[v.sc]=v.fs; } } ll solve(int u,int p,int sl,const vector<ll>&s) { if(sl<0) return MAX_VAL; ll res=0; for(auto v:g[u]) if(v.sc!=p) if(dp[v.sc][0]<=dp[v.sc][1]) { res+=dp[v.sc][0]; }else { res+=dp[v.sc][1]; } for(int i=0;i<(int)s.size()-sl;i++) res+=s[i]; return res; } void DFS(int u,int p) { for(auto v:g[u]) if(v.sc!=p) DFS(v.sc,u); vector<ll>s; for(auto v:g[u]) if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1]) s.pb(dp[v.sc][0]-dp[v.sc][1]); //0 dp[u][0]=solve(u,p,k,s)+cost[u]; //1 dp[u][1]=solve(u,p,k-(u!=0),s); } }nho; ll get(int u,int sl) { if(sl>=sum[u].size()) return 0; if(sl==0) return sum[u].back(); return sum[u].back()-sum[u][sl-1]; } ll solve(int u,int p,int sl,const vector<ll>&s) { if(sl<0) return MAX_VAL; ll cong=0,res=MAX_VAL; for(auto v:edge[u]) if(v.sc!=p) { if(dp[v.sc][0]<=dp[v.sc][1]) { cong+=dp[v.sc][0]; }else { cong+=dp[v.sc][1]; } } if((int)s.size()<=sl) res=min(res,cong+get(u,sl-(int)s.size())); for(int i=0;i<s.size();i++) { cong+=s[i]; if((int)s.size()-i-1<=sl) res=min(res,cong+get(u,sl-((int)s.size()-i-1))); if(sl-((int)s.size()-i-1)>=sum[u].size()) break; } return res; } void DFS(int u,int p) { ktr[u]=k; for(auto v:edge[u]) if(v.sc!=p) { cost[v.sc]=v.fs; DFS(v.sc,u); } vector<ll>s; for(auto v:edge[u]) if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1]) s.pb(dp[v.sc][0]-dp[v.sc][1]); //0 dp[u][0]=solve(u,p,k,s)+cost[u]; //1 dp[u][1]=solve(u,p,k-(p!=-1),s); } vector<long long> minimum_closure_costs(int NNN, vector<int> UUU, vector<int> VVV, vector<int> WWW) { n=NNN; for(int i=0;i<n-1;i++) { int u=UUU[i],v=VVV[i],w=WWW[i]; g[u].pb({w,v}); g[v].pb({w,u}); } cost[0]=1e18; nho.build(0,-1); vector<ll>kq; BLOCKS=sqrt(n); for(int i=0;i<n;i++) spec[i]=((int)g[i].size()>BLOCKS); for(int i=0;i<n-1;i++) { int u=UUU[i],v=VVV[i],w=WWW[i]; tong+=1ll*w; if((int)g[u].size()<(int)g[v].size()) swap(u,v); if(spec[u]&&spec[v]) { edge[u].pb({w,v}); edge[v].pb({w,u}); cnt++; continue; } if(spec[u]) { sum[u].pb(w); continue; } them+=1ll*w; } assert(cnt<=BLOCKS); for(k=0;k<=BLOCKS;k++) { nho.DFS(0,-1); kq.pb(dp[0][1]); } for(int i=0;i<n;i++) { sort(sum[i].begin(),sum[i].end(),greater<ll>()); for(int j=1;j<sum[i].size();j++) sum[i][j]+=sum[i][j-1]; } for(int i=0;i<n;i++) if(spec[i]==1) lis.pb(i); memset(cost,0x3f3f,sizeof(cost)); for(k=BLOCKS+1;k<n;k++) { ll res=0; for(auto u:lis) if(ktr[u]!=k) DFS(u,-1),res+=dp[u][1]; kq.pb(res); } return kq; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; vector<int>U(n-1),V(n-1),W(n-1); for(int i=0;i<n-1;i++) cin>>U[i]>>V[i]>>W[i]; vector<ll>kq=minimum_closure_costs(n,U,V,W); for(auto u:kq)cout<<u<<" "; return 0; } #endif

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

roads.cpp: In member function 'long long int nho::solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:48:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   48 |             if(v.sc!=p)
      |               ^
roads.cpp: In function 'long long int get(int, int)':
roads.cpp:80:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     if(sl>=sum[u].size())
      |        ~~^~~~~~~~~~~~~~~
roads.cpp: In function 'long long int solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
roads.cpp:110:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(sl-((int)s.size()-i-1)>=sum[u].size())
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         for(int j=1;j<sum[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...