Submission #1272012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272012		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;

// Triple DP (see discussion): dp0 = u not chosen, dp1 = u chosen but isolated, dp2 = u chosen and already connected
struct Triple {
    vector<ll> dp0, dp1, dp2;
};

Triple dfs(int u, int p) {
    Triple cur;
    cur.dp0 = {0};       // 0 participants, cost 0, u not chosen
    cur.dp1 = {D[u]};    // u chosen & isolated: currently contributes cost D[u], but not counted as participant
    cur.dp2 = {INF};     // impossible yet (no child connected u)
    int curMax = 0;

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

        int chMax = max({ (int)ch.dp0.size()-1, (int)ch.dp1.size()-1, (int)ch.dp2.size()-1 });
        int newMax = curMax + chMax;
        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));
        }

        vector<ll> n0(newMax+1, INF), n1(newMax+1, INF), n2(newMax+1, INF);

        for (int i = 0; i <= curMax; ++i) {
            ll cur0 = (i < (int)cur.dp0.size()) ? cur.dp0[i] : INF;
            ll cur1 = (i < (int)cur.dp1.size()) ? cur.dp1[i] : INF;
            ll cur2 = (i < (int)cur.dp2.size()) ? cur.dp2[i] : INF;

            for (int j = 0; j <= chMax; ++j) {
                ll ch0 = (j < (int)ch.dp0.size()) ? ch.dp0[j] : INF;
                ll ch1 = (j < (int)ch.dp1.size()) ? ch.dp1[j] : INF;
                ll ch2 = (j < (int)ch.dp2.size()) ? ch.dp2[j] : INF;
                ll bestj = bestChild[j];

                // u not chosen -> child best
                if (cur0 < INF && bestj < INF) n0[i+j] = min(n0[i+j], cur0 + bestj);

                // u chosen but isolated
                if (cur1 < INF) {
                    if (ch0 < INF) n1[i+j] = min(n1[i+j], cur1 + ch0);
                    if (ch1 < INF && i + j + 2 <= newMax) n2[i+j+2] = min(n2[i+j+2], cur1 + ch1);
                    if (ch2 < INF && i + j + 1 <= newMax) n2[i+j+1] = min(n2[i+j+1], cur1 + ch2);
                }

                // u chosen and already connected
                if (cur2 < INF) {
                    if (ch0 < INF) n2[i+j] = min(n2[i+j], cur2 + ch0);
                    if (ch1 < INF && i + j + 1 <= newMax) n2[i+j+1] = min(n2[i+j+1], cur2 + ch1);
                    if (ch2 < INF) n2[i+j] = min(n2[i+j], cur2 + ch2);
                }
            }
        }

        cur.dp0.swap(n0);
        cur.dp1.swap(n1);
        cur.dp2.swap(n2);
        curMax = newMax;
    }

    // after children, cur.dp1 means u chosen but isolated (u not participant)
    // cur.dp2 means u chosen & participant
    // ensure dp sizes / base cases ok
    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);
    }

    vector<char> vis(N, 0);
    vector<vector<ll>> comps; // comps[t] = min cost to get t participants in this component

    for (int i = 0; i < N; ++i) if (!vis[i]) {
        // BFS to mark component nodes
        vector<int> nodes;
        queue<int> q; q.push(i); vis[i]=1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            nodes.push_back(u);
            for (int v : g[u]) if (!vis[v]) { vis[v]=1; q.push(v); }
        }

        // run dfs from nodes[0] as root
        Triple res = dfs(nodes[0], -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));
        }
        comps.push_back(move(best));
    }

    // knapsack combine components
    vector<ll> global(1, 0); // global[0] = 0
    for (auto &best : comps) {
        int s1 = (int)global.size()-1;
        int s2 = (int)best.size()-1;
        vector<ll> ng(s1 + s2 + 1, INF);
        for (int a = 0; a <= s1; ++a) if (global[a] < INF) {
            for (int b = 0; b <= s2; ++b) if (best[b] < INF) {
                ng[a+b] = min(ng[a+b], global[a] + best[b]);
            }
        }
        global.swap(ng);
    }

    // answer queries
    int Q; cin >> Q;
    while (Q--) {
        ll S; cin >> S;
        int lo = 0, hi = (int)global.size()-1, 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