Submission #403317

#	Time	Username	Problem	Language	Result	Execution time	Memory
403317		CrouchingDragon	Džumbus (COCI19_dzumbus)	C++17	0 / 110	41 ms	2316 KiB

dzumbus

#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> D(N);
    for (auto& x : D) cin >> x;

    vector<vector<int>> E(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        E[u].push_back(v), E[v].push_back(u);
    }

    vector<ll> comp;

    vector<bool> vis(N, false);
    auto dfs = [&](auto&& self, int u, int p) -> vector<array<ll, 2>> {
        vis[u] = true;
        vector<array<ll, 2>> dp = {{0LL, D[u]}};
        for (auto v : E[u]) if (v != p) {
            auto dpv = self(self, v, u);
            int k = (int)size(dp), l = (int)size(dpv);
            vector<array<ll, 2>> dpnxt(k + l, {LINF, LINF});
            for (int i = 0; i < k; ++i) {
                for (int j = 0; j < l; ++j) {
                    for (auto s : {0, 1}) {
                        for (auto t : {0, 1}) {
                            int b = s & t;
                            dpnxt[i + j + b][s] = min(dpnxt[i + j + b][s], dp[i][s] + dpv[j][t]);
                        }
                    }
                }
            }
            swap(dp, dpnxt);
        }
        for (int i = 0; i < (int)size(dp); ++i) {
            comp[i] = min({comp[i], dp[i][0], dp[i][1]});
        }
        return dp;
    };

    vector<ll> dp(1, LINF);
    dp[0] = 0;

    for (int u = 0; u < N; ++u) {
        if (vis[u]) continue;
        comp.assign(N + 1, LINF);
        dfs(dfs, u, -1);
        comp.erase(lower_bound(all(comp), LINF), end(comp));
        int k = (int)size(dp), l = (int)size(comp);
        vector<ll> dpnxt(k + l - 1, LINF);
        for (int i = 0; i < k; ++i) {
            for (int j = 1; j < l; ++j) {
                dpnxt[i + j] = min(dpnxt[i + j], dp[i] + comp[j]);
            }
        }
        swap(dp, dpnxt);
    }

    int Q;
    cin >> Q;
    for (int z = 0; z < Q; ++z) {
        ll S;
        cin >> S;
        int ans = (int)distance(begin(dp), upper_bound(all(dp), S));
        cout << ans << endl;
    }

    exit(0);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30