Submission #1272018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272018		sweetwibu2k8	Džumbus (COCI19_dzumbus)	C++20	0 / 110	27 ms	2776 KiB

dzumbus

// dzumbus_fixed.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

int N, M;
vector<ll> D;
vector<vector<int>> g;

struct Triple {
    vector<ll> dp0; // u not chosen: dp0[k] = min cost to have k good nodes in subtree
    vector<ll> dp1; // u chosen but not yet satisfied by child (pending): dp1[k] = min cost, k good nodes in subtree (not counting u)
    vector<ll> dp2; // u chosen and already satisfied by some child (so u is counted): dp2[k] = min cost, k good nodes in subtree (including u)
};

Triple dfs(int u, int p){
    Triple cur;
    cur.dp0 = {0};        // 0 good nodes, cost 0
    cur.dp1 = {D[u]};     // 0 good nodes yet, but u chosen cost D[u]
    cur.dp2 = {};         // impossible initially

    for (int v : g[u]) if (v != p){
        Triple ch = dfs(v, u);

        int s0 = (int)cur.dp0.size() - 1;
        int s1 = (int)cur.dp1.size() - 1;
        int s2 = (int)cur.dp2.size() - 1;
        int c0 = (int)ch.dp0.size() - 1;
        int c1 = (int)ch.dp1.size() - 1;
        int c2 = (int)ch.dp2.size() - 1;

        int maxc_for_any = max({c0, c1, c2, 0});
        int new_max = max({s0, s1, s2, 0}) + maxc_for_any + 2; // +2 to be safe for transitions that add +2

        vector<ll> ndp0(new_max+1, INF), ndp1(new_max+1, INF), ndp2(new_max+1, INF);

        auto cost = [&](const vector<ll> &vec, int j)->ll{
            if (j < 0) return INF;
            if (j >= (int)vec.size()) return INF;
            return vec[j];
        };

        // Merge for dp0: parent not chosen -> child can be in dp0 or dp2
        for (int i = 0; i <= s0; ++i){
            ll base = cost(cur.dp0, i);
            if (base >= INF) continue;
            for (int j = 0; j <= max(c0, c2); ++j){
                ll cst = min(cost(ch.dp0, j), cost(ch.dp2, j));
                if (cst >= INF) continue;
                ndp0[i + j] = min(ndp0[i + j], base + cst);
            }
        }

        // Merge for dp1: parent chosen but pending -> child dp0 or dp2 keeps parent pending
        // child dp1 connects parent and child -> goes to dp2 and adds +2 (child becomes good +1, parent becomes good +1)
        for (int i = 0; i <= s1; ++i){
            ll base = cost(cur.dp1, i);
            if (base >= INF) continue;
            for (int j = 0; j <= max({c0,c1,c2}); ++j){
                // child dp0
                if (cost(ch.dp0, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + cost(ch.dp0, j));
                // child dp2
                if (cost(ch.dp2, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + cost(ch.dp2, j));
                // child dp1 => resolves both child and parent -> move to dp2
                if (cost(ch.dp1, j) < INF){
                    ndp2[i + j + 2] = min(ndp2[i + j + 2], base + cost(ch.dp1, j));
                }
            }
        }

        // Merge for dp2: parent already satisfied -> child dp0 or dp2 add j goods; child dp1 will be satisfied by parent and add +1
        if (!cur.dp2.empty()){
            for (int i = 0; i <= s2; ++i){
                ll base = cost(cur.dp2, i);
                if (base >= INF) continue;
                for (int j = 0; j <= max({c0,c1,c2}); ++j){
                    if (cost(ch.dp0, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + cost(ch.dp0, j));
                    if (cost(ch.dp2, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + cost(ch.dp2, j));
                    if (cost(ch.dp1, j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], base + cost(ch.dp1, j));
                }
            }
        }

        // Trim trailing INF and assign back
        auto trim = [&](vector<ll> &v){
            int last = (int)v.size() - 1;
            while (last >= 0 && v[last] >= INF) --last;
            v.resize(last+1);
        };
        trim(ndp0); trim(ndp1); trim(ndp2);
        if (ndp0.empty()) ndp0 = {INF};
        if (ndp1.empty()) ndp1 = {INF};
        // ndp2 may legitimately be empty

        cur.dp0.swap(ndp0);
        cur.dp1.swap(ndp1);
        cur.dp2.swap(ndp2);
    }

    return cur;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> M)) return 0;
    D.assign(N, 0);
    for (int i = 0; i < N; ++i) cin >> D[i];
    g.assign(N, {});
    for (int i = 0; i < M; ++i){
        int a,b; cin >> a >> b; --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int Q; cin >> Q;
    vector<ll> S(Q);
    for (int i = 0; i < Q; ++i) cin >> S[i];

    vector<int> vis(N, 0);
    vector<vector<ll>> comps;
    for (int i = 0; i < N; ++i) if (!vis[i]){
        // collect component nodes
        vector<int> stack = {i};
        vis[i] = 1;
        for (int idx = 0; idx < (int)stack.size(); ++idx){
            int u = stack[idx];
            for (int v : g[u]) if (!vis[v]){ vis[v] = 1; stack.push_back(v); }
        }
        // run dfs dp with root i
        Triple t = dfs(i, -1);
        int maxc = 0;
        if (!t.dp0.empty()) maxc = max(maxc, (int)t.dp0.size()-1);
        if (!t.dp2.empty()) maxc = max(maxc, (int)t.dp2.size()-1);
        vector<ll> best(maxc+1, INF);
        for (int c = 0; c <= maxc; ++c){
            ll val = INF;
            if (c < (int)t.dp0.size()) val = min(val, t.dp0[c]);
            if (c < (int)t.dp2.size()) val = min(val, t.dp2[c]);
            best[c] = val;
        }
        // ensure best[0]=0
        if (best.size() == 0) best = {0};
        else best[0] = min(best[0], 0LL);
        comps.push_back(best);
    }

    // global knapsack by value
    vector<ll> dp(N+1, INF);
    dp[0] = 0;
    for (auto &best : comps){
        vector<ll> ndp(N+1, INF);
        int sz = (int)best.size() - 1;
        for (int have = 0; have <= N; ++have){
            if (dp[have] >= INF) continue;
            for (int c = 0; c <= sz; ++c){
                if (best[c] >= INF) continue;
                if (have + c <= N) ndp[have + c] = min(ndp[have + c], dp[have] + best[c]);
            }
        }
        dp.swap(ndp);
    }

    for (int qi = 0; qi < Q; ++qi){
        ll s = S[qi];
        int ans = 0;
        for (int v = 0; v <= N; ++v) if (dp[v] <= s) ans = v;
        cout << ans << "\n";
    }
    return 0;
}

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