Submission #156490

#	Time	Username	Problem	Language	Result	Execution time	Memory
156490		lyc	Museum (CEOI17_museum)	C++14	100 / 100	942 ms	785164 KiB

museum

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 10005;
int N, K, X, A, B, C;
vector<ii> al[MX_N];
int f[MX_N][MX_N][2], g[MX_N];

void dfs(int u, int p) {
    g[u] = 1;
    f[u][1][0] = f[u][1][1] = 0;
    for (auto v : al[u]) if (v.fi != p) {
        dfs(v.fi,u);
        RFOR(j,g[u],1) FOR(k,1,g[v.fi]){
            f[u][j+k][0] = min(f[u][j+k][0], f[u][j][0] + f[v.fi][k][0] + 2*v.sc);
            f[u][j+k][1] = min(f[u][j+k][1], f[u][j][0] + f[v.fi][k][1] + v.sc);
            f[u][j+k][1] = min(f[u][j+k][1], f[u][j][1] + f[v.fi][k][0] + 2*v.sc);
        }
        g[u] += g[v.fi];
    }
    //printf("%d (%d):\n", u, g[u]);
    //FOR(j,0,g[u]) printf("%d ", f[u][j][0]);
    //printf("\n");
    //FOR(j,0,g[u]) printf("%d ", f[u][j][1]);
    //printf("\n");
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K >> X;
    memset(f,63,sizeof f);
    FOR(i,1,N-1){ cin >> A >> B >> C; al[A].emplace_back(B,C); al[B].emplace_back(A,C); }
    dfs(X,0);
    cout << f[X][K][1] << '\n';
}

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