Submission #1276729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276729		herominhsteve	Museum (CEOI17_museum)	C++20	100 / 100	475 ms	784608 KiB

museum

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "MUSEUM"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1e4 + 1;
const long long INF = (long long) 1e16 + 15092007;

struct Edges{
    int v,w;
    Edges(): v(0),w(0) {}
    Edges(int V,int W):v(V),w(W) {}
    bool operator < (const Edges &other) const{
        return w>other.w;
    }
};

int n,K,S;
vector<Edges> graph[MAXN];

void init(){
	cin>>n>>K>>S;
    if (K==1){
        cout<<0;
        exit(0);
    }
    for (int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].emplace_back(v,w);
        graph[v].emplace_back(u,w);
    }
}

int sz[MAXN];

/*
 * dp[u][k][*]: minimum time to visit K nodes in U'S subtree
 * 0 = starting and ending at U
 * 1 = starting at U and ending at anywhere
*/

int dp[MAXN][MAXN][2];

void dfs(int u,int pre){
    sz[u] = 1;
    dp[u][1][0] = dp[u][1][1] = 0;
    for (Edges x : graph[u]){
        int v = x.v;
        int w = x.w;
        if (v==pre) continue;
        dfs(v,u);
        for (int i = min(K,sz[u]); i>=1;i--){
            for (int j = min(K-i,sz[v]); j>=1; j--){
                minimize(dp[u][i+j][0], dp[u][i][0] + dp[v][j][0] + 2 * w );
                int sumFree = min(dp[u][i][0] + dp[v][j][1] + w,
                                        dp[u][i][1] + dp[v][j][0] + 2 * w );
                minimize(dp[u][i+j][1], sumFree);
            }
        }
        sz[u] += sz[v];
    }
}

void sol(){
	mset(dp,0x3f3f3f3f);
    dfs(S,S);
    cout<<min(dp[S][K][0],dp[S][K][1]);
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

museum.cpp: In function 'void setup()':
museum.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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