Submission #1272016

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

dzumbus

#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;
vector<int> seen;

// DP returns triple of vectors dp0, dp1, dp2 for node u
// dp*_sz = number of possible good nodes in subtree (indices 0..sz)
struct Triple {
    vector<ll> dp0, dp1, dp2;
};

Triple dfs(int u, int p) {
    // initialize
    Triple cur;
    cur.dp0 = vector<ll>(1, 0);         // if u not chosen: 0 cost, 0 good nodes
    cur.dp1 = vector<ll>(1, D[u]);      // if u chosen but not connected yet: cost D[u], 0 good nodes inside so far
    cur.dp2 = vector<ll>();             // empty until it becomes possible
    int size_cur = 0; // number of good nodes accounted so far in these arrays

    for (int v : g[u]) if (v != p) {
        Triple ch = dfs(v, u);
        int s1 = size_cur;
        int s2 = (int)max({ch.dp0.size(), ch.dp1.size(), ch.dp2.size()}) - 1;
        int new_size = s1 + s2;

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

        // Helper: get cost arrays for child states (if index j out of range, cost = INF)
        auto cost0 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp0.size()) ? ch.dp0[j] : INF; };
        auto cost1 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp1.size()) ? ch.dp1[j] : INF; };
        auto cost2 = [&](int j)->ll { return (j >= 0 && j < (int)ch.dp2.size()) ? ch.dp2[j] : INF; };

        // Merge for dp0: parent not chosen -> child may be dp0 or dp2 only
        for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp0.size()) {
            if (cur.dp0[i] >= INF) continue;
            for (int j = 0; j <= s2; ++j) {
                ll candi = min(cost0(j), cost2(j));
                if (candi >= INF) continue;
                ndp0[i+j] = min(ndp0[i+j], cur.dp0[i] + candi);
            }
        }

        // Merge for dp2 (parent already connected): child can be dp0, dp2, or dp1 (dp1 resolves to +1 count)
        if (!cur.dp2.empty()) {
            for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp2.size()) {
                if (cur.dp2[i] >= INF) continue;
                for (int j = 0; j <= s2; ++j) {
                    // child dp0 or dp2: counts add j
                    if (cost0(j) < INF) ndp2[i+j] = min(ndp2[i+j], cur.dp2[i] + cost0(j));
                    if (cost2(j) < INF) ndp2[i+j] = min(ndp2[i+j], cur.dp2[i] + cost2(j));
                    // child dp1: when parent is selected, child pending resolves: child contributes +1
                    if (cost1(j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], cur.dp2[i] + cost1(j));
                }
            }
        }

        // Merge for dp1 (parent chosen but not connected yet)
        for (int i = 0; i <= s1; ++i) if (i < (int)cur.dp1.size()) {
            if (cur.dp1[i] >= INF) continue;
            for (int j = 0; j <= s2; ++j) {
                // child dp0 or dp2: parent remains pending
                if (cost0(j) < INF) ndp1[i+j] = min(ndp1[i+j], cur.dp1[i] + cost0(j));
                if (cost2(j) < INF) ndp1[i+j] = min(ndp1[i+j], cur.dp1[i] + cost2(j));
                // child dp1: connecting parent and child => parent becomes connected (+1), child becomes good (+1)
                if (cost1(j) < INF) {
                    // added good nodes: child gives j+1, plus parent +1 -> total + (j+2)
                    ndp2[i + j + 2] = min(ndp2[i + j + 2], cur.dp1[i] + cost1(j));
                }
            }
        }

        // Also dp2 could be created from dp0 if dp0 was empty? No: dp0 cannot create dp2.
        // Update cur with ndp*
        // Trim trailing INF entries possibly to reduce sizes
        auto trim = [&](vector<ll> &v) {
            int last = (int)v.size() - 1;
            while (last >= 0 && v[last] >= INF) --last;
            v.resize(last+1);
            if (v.empty()) v = vector<ll>(); // keep empty
        };

        cur.dp0 = ndp0; trim(cur.dp0);
        cur.dp1 = ndp1; trim(cur.dp1);
        cur.dp2 = ndp2; trim(cur.dp2);
        size_cur = (int)max({cur.dp0.size(), cur.dp1.size(), cur.dp2.size()}) - 1;
        if (size_cur < 0) size_cur = 0;
    } // end foreach child

    return cur;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    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);
    ll Smax = 0;
    for (int i = 0; i < Q; ++i) { cin >> S[i]; Smax = max(Smax, S[i]); }

    // find components and compute best_comp for each
    vector<int> vis(N,0);
    vector<vector<ll>> comps_best; // comps_best[k][c] = minimal cost to get c good nodes in that comp

    for (int i = 0; i < N; ++i) if (!vis[i]) {
        // BFS/DFS to mark 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 tree DP with root = i (component is a tree by problem statement)
        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);
        // best[c] = min(dp0[c], dp2[c]) (dp1 invalid at root)
        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;
        }
        // also possible to take c=0 with cost 0 even if not present
        if (best.size() == 0) best = vector<ll>(1, 0);
        else best[0] = min(best[0], 0LL);
        comps_best.push_back(best);
    }

    // global knapsack by value: dp[v] = minimal cost to achieve total v good nodes across processed components
    vector<ll> global(N+1, INF);
    global[0] = 0;
    for (auto &best : comps_best) {
        int sz = (int)best.size()-1;
        vector<ll> nxt(N+1, INF);
        for (int have = 0; have <= N; ++have) {
            if (global[have] >= INF) continue;
            // take c from this comp
            for (int c = 0; c <= sz; ++c) {
                if (best[c] >= INF) continue;
                if (have + c <= N) nxt[have + c] = min(nxt[have + c], global[have] + best[c]);
            }
        }
        global.swap(nxt);
    }

    // For each query S[i], find max v with global[v] <= S[i]
    for (int qi = 0; qi < Q; ++qi) {
        ll s = S[qi];
        int ans = 0;
        for (int v = 0; v <= N; ++v) {
            if (global[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