Submission #202103

#	Time	Username	Problem	Language	Result	Execution time	Memory
202103		thebes	Museum (CEOI17_museum)	C++14	100 / 100	867 ms	784928 KiB

museum

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

#define pb push_back

const int MN = 1e4+5;
int N, K, X, i, j, x, y, w, dp[MN][MN], dp2[MN][MN], tmp[MN], tmp2[MN], sz[MN];
vector<pii> adj[MN];

void dfs(int n,int p){
    memset(dp[n],0x3f,sizeof(dp[n]));
    memset(dp2[n],0x3f,sizeof(dp2[n]));
    dp[n][0]=dp[n][1]=dp2[n][0]=dp2[n][1]=0;
    sz[n] = 1;
    for(auto v : adj[n]){
        if(v.first==p) continue;
        dfs(v.first, n);
        memset(tmp,0x3f,sizeof(tmp));
        memset(tmp2,0x3f,sizeof(tmp2));
        for(i=0;i<=sz[n];i++){
            for(j=0;j<=sz[v.first];j++){
                tmp[i+j]=min(tmp[i+j],dp[n][i]+dp[v.first][j]+2*v.second);
                tmp2[i+j]=min(tmp2[i+j],min(dp[n][i]+dp2[v.first][j]+v.second,dp2[n][i]+dp[v.first][j]+2*v.second));
            }
        }
        sz[n] += sz[v.first];
        for(i=0;i<=sz[n];i++){
            dp[n][i]=min(dp[n][i],tmp[i]);
            dp2[n][i]=min(dp2[n][i],tmp2[i]);
        }
    }
}

int main(){
    scanf("%d%d%d",&N,&K,&X);
    for(i=1;i<N;i++){
        scanf("%d%d%d",&x,&y,&w);
        adj[x].pb({y,w});
        adj[y].pb({x,w});
    }
    dfs(X,0);
    printf("%d\n",min(dp[X][K],dp2[X][K]));
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&N,&K,&X);
     ~~~~~^~~~~~~~~~~~~~~~~~~
museum.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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