Submission #1209043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209043		btninh	Museum (CEOI17_museum)	C++20	80 / 100	149 ms	17992 KiB

museum

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

#define btninh signed main
#define int long long
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define fast ios::sync_with_stdio(0); cin.tie(0)
#define IO(x) if(fopen(x".inp","r")){freopen(x".inp","r",stdin);freopen(x".out","w",stdout);}
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
template<class T> bool mini(T &x, T y){if (x > y) return x = y, true; return false;}
template<class T> bool maxi(T &x, T y){if (x < y) return x = y, true; return false;}
const int N = 10005;
const int inf = 1e9;
const int mod = 1e9 + 7;

int n, k, x, dp[N][105][2], sum[N], sz[N];
vector<pii> g[N];

void dfs(int u, int p = -1){
	for(auto [v, w] : g[u]){
		if (v == p) continue;
		sum[v] = sum[u] + w;
		dfs(v, u);
	}
}

void calc(int u, int p = -1){
    dp[u][0][0] = dp[u][1][0] = 0;
    dp[u][1][1] = -sum[u];
    sz[u] = 1;
    for(auto [v, w] : g[u]){
        if (v == p) continue;
        calc(v, u);
        FORD(i, sz[u], 0){
            FOR(j, 0, sz[v]) {
                if (i + j > k) continue;
                int c = (j > 0 ? 2 * w : 0);
                mini(dp[u][i + j][0], dp[u][i][0] + dp[v][j][0] + c);
                mini(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0] + c);
                mini(dp[u][i + j][1], dp[u][i][0] + dp[v][j][1] + c);
            }
        }
        sz[u] += sz[v];
    }
}

btninh(){
    fast;
    //IO("main");
    
    cin >> n >> k >> x;
    FOR(i, 1, n - 1){
    	int u, v, w;
    	cin >> u >> v >> w;
    	g[u].pb({v, w});
    	g[v].pb({u, w});
    }
    dfs(x);
    memset(dp, 0x3f3f3f, sizeof dp);
    calc(x);
    cout << dp[x][k][1];
}

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