Submission #1248122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248122		quocbaoo	Museum (CEOI17_museum)	C++20	100 / 100	426 ms	746336 KiB

museum

#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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20