Submission #1248122

#TimeUsernameProblemLanguageResultExecution timeMemory
1248122quocbaooMuseum (CEOI17_museum)C++20
100 / 100
426 ms746336 KiB
#include<bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int N=1e4,INF=5e8+9; int n,dp[N+5][N+5][2],sz[N+5]; vector<pair<int,int>> g[N+5]; void dfs(int u,int pa){ dp[u][1][0]=0;dp[u][1][1]=0;sz[u]=1; for (auto j:g[u]){ if (j.fi==pa) continue; dfs(j.fi,u); for (int j1=sz[u];j1>=1;j1--){ for (int j2=sz[j.fi];j2>=1;j2--){ dp[u][j1+j2][0]=min(dp[u][j1+j2][0],dp[u][j1][0]+dp[j.fi][j2][0]+2*j.se); dp[u][j1+j2][1]=min(dp[u][j1+j2][1],dp[u][j1][1]+dp[j.fi][j2][0]+2*j.se); dp[u][j1+j2][1]=min(dp[u][j1+j2][1],dp[u][j1][0]+dp[j.fi][j2][1]+j.se); } } sz[u]+=sz[j.fi]; } } int main(){ if (fopen("museum.inp","r")){ freopen("museum.inp","r",stdin); freopen("museum.out","w",stdout); } ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; int k,x;cin>>k>>x; for (int i=1;i<n;i++){ int u,v,w;cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } for (int i=1;i<=n;i++){ for (int j=0;j<=k;j++) dp[i][j][0]=INF,dp[i][j][1]=INF; } dfs(x,x); cout<<dp[x][k][1]; }

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("museum.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen("museum.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...