Submission #1084622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084622		ShaShi	Museum (CEOI17_museum)	C++17	100 / 100	419 ms	310828 KiB

museum

#include <bits/stdc++.h>
 
#define int long long
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
const int MAXN = (int)1e4 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e18 + 7;
const int LG = 20;


int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], arr2[MAXN], sz[MAXN];
vector<pii> adj[MAXN];
vector<int> dp[2][MAXN];


void DFS(int v, int p=0) {
    dp[0][v] = {0, 0}; dp[1][v] = {0, 0}; sz[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;

        if (u == p) continue;

        DFS(u, v);

        vector<int> pd[2]; 
        pd[0].resize(sz[v]+sz[u]+1); fill(all(pd[0]), INF);
        pd[1].resize(sz[v]+sz[u]+1); fill(all(pd[1]), INF);

        for (int x=0; x<=sz[v]; x++) {
            for (int y=0; y<=sz[u]; y++) {
                pd[1][x+y] = min(pd[1][x+y], dp[1][v][x]+dp[1][u][y]+2*w);
                pd[0][x+y] = min(pd[0][x+y], dp[1][v][x]+dp[0][u][y]+w);
                pd[0][x+y] = min(pd[0][x+y], dp[0][v][x]+dp[1][u][y]+2*w);

                if (!y) pd[1][x] = min(pd[1][x], dp[1][v][x]);
                if (!y) pd[0][x] = min(pd[0][x], dp[0][v][x]);
            }
        }

        dp[0][v] = pd[0]; dp[1][v] = pd[1]; sz[v] += sz[u];
    }
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> k >> m;

    for (int i=1; i<n; i++) {
        cin >> u >> v >> w;

        adj[u].pb({v, w}); adj[v].pb({u, w});
    }

    DFS(m);

    cout << dp[0][m][k] << endl;


    return 0;
}

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