Submission #922336

#	Time	Username	Problem	Language	Result	Execution time	Memory
922336		phong	Museum (CEOI17_museum)	C++17	100 / 100	303 ms	785676 KiB

museum

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e4 + 5;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

int n, k, x;
int a[nmax];

vector<pii> adj[nmax];
int sz[nmax], f[nmax][nmax][2], tmp[nmax][2];
void ckmin(int &a, int b){
    a = min(a, b);
}
void dfs(int u, int p){
    sz[u] = 1;
    f[u][1][0] = a[u] * 2;
    f[u][1][1] = a[u];
    for(auto [w, v] : adj[u]){
        if(v == p) continue;
        a[v] = w;
        dfs(v, u);
        for(int i = 0; i <= sz[u]; ++i){
            tmp[i][0] = f[u][i][0];
            tmp[i][1] = f[u][i][1];
        }
        for(int x = 0; x <= sz[u]; ++x){
            for(int y = 0; y <= sz[v]; ++y){
                if(x + y > k) continue;
                ckmin(f[u][x + y][0], tmp[x][0] + f[v][y][0]);
                ckmin(f[u][x + y][1], tmp[x][0] + f[v][y][1] - a[u]);
                ckmin(f[u][x + y][1], tmp[x][1] + f[v][y][0]);
            }
        }
        sz[u] += sz[v];
    }
}
void update(){
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.ans", "w", stdout);
    cin >> n >> k >> x;
//    k = n - k;
    for(int i = 1, u, v, w; i < n; ++i){
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }
    memset(f, 0x3f, sizeof f);
    dfs(x, -1);
    cout << f[x][k][1];
}
/*
5 3 2
2 3 3
3 5 5
5 1 6
5 4 3


*/

Compilation message (stderr)

museum.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

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