Submission #1272013

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

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;

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

// DP arrays per node: we'll return a triple of vectors
// dp0: u not chosen -> dp0[p] = min cost to have p participants in subtree
// dp1: u chosen but currently isolated (not participant yet) -> dp1[p] = min cost
// dp2: u chosen and already connected (participant) -> dp2[p] = min cost
struct Triple {
    vector<ll> dp0, dp1, dp2;
};

Triple dfs(int u, int parent) {
    // initialize
    Triple cur;
    cur.dp0 = {0};            // 0 participants, cost 0, u not chosen
    cur.dp1 = {D[u]};         // 0 participants but u chosen and isolated (cost D[u])
    cur.dp2 = {INF};          // impossible initially (no children yet to connect u)
    int cursz = 0; // maximum participants count currently possible

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

        // for child ch, bestChild[j] = min(ch.dp0[j], ch.dp1[j], ch.dp2[j])
        int chMax = max({ (int)ch.dp0.size()-1, (int)ch.dp1.size()-1, (int)ch.dp2.size()-1 });
        vector<ll> bestChild(chMax+1, INF);
        for (int j = 0; j <= chMax; ++j) {
            ll a = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
            ll b = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
            ll c = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
            bestChild[j] = min(a, min(b, c));
        }

        int newMax = cursz + chMax;
        vector<ll> n0(newMax+1, INF), n1(newMax+1, INF), n2(newMax+1, INF);

        // iterate over current i and child j and combine
        for (int i = 0; i <= cursz; ++i) {
            // values from cur
            ll cur0_i = (i < (int)cur.dp0.size()) ? cur.dp0[i] : INF;
            ll cur1_i = (i < (int)cur.dp1.size()) ? cur.dp1[i] : INF;
            ll cur2_i = (i < (int)cur.dp2.size()) ? cur.dp2[i] : INF;

            for (int j = 0; j <= chMax; ++j) {
                // child's three states
                ll ch0_j = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
                ll ch1_j = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
                ll ch2_j = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
                ll best_j = bestChild[j];

                // 1) u not chosen (cur0) -> remains not chosen; child best
                if (cur0_i < INF && best_j < INF) {
                    ll val = cur0_i + best_j;
                    n0[i + j] = min(n0[i + j], val);
                }

                // 2) u chosen but isolated so far (cur1)
                if (cur1_i < INF) {
                    // if child not selected at root (ch0): u stays isolated
                    if (ch0_j < INF) {
                        n1[i + j] = min(n1[i + j], cur1_i + ch0_j);
                    }
                    // if child root selected but isolated (ch1): connecting u<->child
                    // => child root becomes participant (+1), u becomes connected (+1)
                    if (ch1_j < INF) {
                        // participants increase by 2
                        if (i + j + 2 <= newMax)
                            n2[i + j + 2] = min(n2[i + j + 2], cur1_i + ch1_j);
                    }
                    // if child root already connected (ch2): child counted, u becomes connected (+1)
                    if (ch2_j < INF) {
                        if (i + j + 1 <= newMax)
                            n2[i + j + 1] = min(n2[i + j + 1], cur1_i + ch2_j);
                    }
                }

                // 3) u chosen and already connected (cur2)
                if (cur2_i < INF) {
                    // child not selected root
                    if (ch0_j < INF) {
                        n2[i + j] = min(n2[i + j], cur2_i + ch0_j);
                    }
                    // child root selected but isolated -> it becomes connected to u => +1 participant
                    if (ch1_j < INF) {
                        if (i + j + 1 <= newMax)
                            n2[i + j + 1] = min(n2[i + j + 1], cur2_i + ch1_j);
                    }
                    // child root already connected
                    if (ch2_j < INF) {
                        n2[i + j] = min(n2[i + j], cur2_i + ch2_j);
                    }
                }
            }
        }

        // move new arrays to cur
        cur.dp0.swap(n0);
        cur.dp1.swap(n1);
        cur.dp2.swap(n2);
        cursz = newMax;
    }

    // After processing children, arrays cur are ready.
    // Note: cur.dp1 currently stores cost where u is chosen but isolated (u not counted).
    // cur.dp2 stores cost where u is chosen and already counted.
    // cur.dp0 stores cost where u not chosen.

    // It's possible cur.dp2 has size 0 (if no possibility) - that's fine.
    return cur;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if 0
    // For local testing: redirect input files here if needed
    freopen("input.txt","r",stdin);
#endif

    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);
    }

    // find components (trees) and compute best vector per component
    vector<char> vis(N, 0);
    vector<vector<ll>> comps; // comps[t] = vector best[t] minimal cost to get t participants in this component

    for (int i = 0; i < N; ++i) {
        if (vis[i]) continue;
        // BFS to collect component nodes (optional) and mark visited
        vector<int> compNodes;
        queue<int> q; q.push(i); vis[i]=1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            compNodes.push_back(u);
            for (int v: g[u]) if (!vis[v]) { vis[v]=1; q.push(v); }
        }
        // run dfs DP rooted at i (tree assumption)
        Triple res = dfs(i, -1);
        int mx = max({ (int)res.dp0.size()-1, (int)res.dp1.size()-1, (int)res.dp2.size()-1 });
        vector<ll> best(mx+1, INF);
        for (int t = 0; t <= mx; ++t) {
            ll a = (t < (int)res.dp0.size()) ? res.dp0[t] : INF;
            ll b = (t < (int)res.dp1.size()) ? res.dp1[t] : INF;
            ll c = (t < (int)res.dp2.size()) ? res.dp2[t] : INF;
            best[t] = min(a, min(b, c));
        }
        // Note: for root, dp1 means root chosen but isolated -> root not participant, that's already accounted.
        comps.push_back(move(best));
    }

    // knapsack combine components: global[k] = min cost to have k participants across processed comps
    vector<ll> global(1, 0); // global[0]=0
    for (auto &best : comps) {
        int sz1 = (int)global.size()-1;
        int sz2 = (int)best.size()-1;
        vector<ll> ng(sz1 + sz2 + 1, INF);
        for (int a = 0; a <= sz1; ++a) if (global[a] < INF) {
            for (int b = 0; b <= sz2; ++b) if (best[b] < INF) {
                ng[a+b] = min(ng[a+b], global[a] + best[b]);
            }
        }
        global.swap(ng);
    }

    // ensure global is nondecreasing in k (should be but numeric INF may cause gaps)
    int maxK = (int)global.size()-1;
    // For binary searching: global[k] is minimal cost for exactly k participants.
    // cost should be nondecreasing; still we keep as is.

    int Q; cin >> Q;
    while (Q--) {
        ll S; cin >> S;
        // find largest k such that global[k] <= S
        int lo = 0, hi = maxK, ans = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (global[mid] <= S) {
                ans = mid;
                lo = mid + 1;
            } else hi = mid - 1;
        }
        cout << ans << '\n';
    }

    return 0;
}

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