제출 #734276

#제출 시각아이디문제언어결과실행 시간메모리
734276bin9638도로 폐쇄 (APIO21_roads)C++17
24 / 100
2080 ms16436 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 int k,n; vector<ii>g[N]; ll cost[N],dp[N][2]; 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) { if(sl<0) return 2e14; ll res=0; // cout<<u<<" "<<p<<" "<<sl<<endl; vector<ll>s; 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]; s.pb(dp[v.sc][0]-dp[v.sc][1]); } //cout<<u<<" "<<p<<" "<<sl<<" "<<s.size()<<endl; sort(s.begin(),s.end()); for(int i=0;i<(int)s.size()-sl;i++) res+=s[i]; return res; } void DFS(int u,int p) { // cout<<u<<" "<<k<<endl; for(auto v:g[u]) if(v.sc!=p) DFS(v.sc,u); //0 dp[u][0]=solve(u,p,k)+cost[u]; //1 dp[u][1]=solve(u,p,k-(u!=0)); } 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; build(0,-1); vector<ll>kq; for(k=0;k<n;k++) { memset(dp,0x3f3f,sizeof(dp)); DFS(0,-1); kq.pb(dp[0][1]); } 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 function 'long long int solve(int, int, int)':
roads.cpp:39:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   39 |         if(v.sc!=p)
      |           ^
#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...