Submission #1272025

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

dzumbus

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const long long INF = 1e18;

int N, M;
int D[MAXN];
vector<int> graph[MAXN];
bool visited[MAXN];
vector<int> components[MAXN];
int comp_index;
long long dp[MAXN];

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> D[i];
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    memset(visited, false, sizeof(visited));
    comp_index = 0;
    for (int i = 1; i <= N; i++) {
        if (!visited[i] && !graph[i].empty()) {
            queue<int> q;
            q.push(i);
            visited[i] = true;
            components[comp_index].push_back(i);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : graph[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        components[comp_index].push_back(v);
                        q.push(v);
                    }
                }
            }
            comp_index++;
        }
    }

    for (int s = 0; s <= N; s++) {
        dp[s] = INF;
    }
    dp[0] = 0;

    for (int i = 0; i < comp_index; i++) {
        vector<int> comp = components[i];
        int L = comp.size();
        if (L < 2) continue;

        map<int, int> global_to_local;
        vector<int> cost_local(L);
        for (int j = 0; j < L; j++) {
            int global_node = comp[j];
            global_to_local[global_node] = j;
            cost_local[j] = D[global_node];
        }

        vector<vector<int>> adj_local(L);
        for (int j = 0; j < L; j++) {
            int global_node = comp[j];
            for (int neighbor : graph[global_node]) {
                if (global_to_local.find(neighbor) != global_to_local.end()) {
                    int k = global_to_local[neighbor];
                    adj_local[j].push_back(k);
                }
            }
        }

        vector<long long> comp_cost(L+1, INF);

        if (L <= 20) {
            for (int mask = 0; mask < (1 << L); mask++) {
                int count = 0;
                long long cost = 0;
                for (int j = 0; j < L; j++) {
                    if (mask & (1 << j)) {
                        count++;
                        cost += cost_local[j];
                    }
                }
                bool valid = true;
                for (int j = 0; j < L; j++) {
                    if (mask & (1 << j)) {
                        bool has_neighbor = false;
                        for (int k : adj_local[j]) {
                            if (mask & (1 << k)) {
                                has_neighbor = true;
                                break;
                            }
                        }
                        if (!has_neighbor) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (valid) {
                    if (cost < comp_cost[count]) {
                        comp_cost[count] = cost;
                    }
                }
            }
        } else {
            vector<pair<int, int>> edges;
            for (int j = 0; j < L; j++) {
                for (int k : adj_local[j]) {
                    if (j < k) {
                        edges.push_back({j, k});
                    }
                }
            }
            sort(edges.begin(), edges.end(), [&](const pair<int, int> &e1, const pair<int, int> &e2) {
                long long cost1 = cost_local[e1.first] + cost_local[e1.second];
                long long cost2 = cost_local[e2.first] + cost_local[e2.second];
                return cost1 < cost2;
            });
            int K = min(50, (int)edges.size());
            for (int e_idx = 0; e_idx < K; e_idx++) {
                int u = edges[e_idx].first;
                int v = edges[e_idx].second;
                vector<bool> inS(L, false);
                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
                inS[u] = true;
                inS[v] = true;
                long long cost_total = cost_local[u] + cost_local[v];
                if (cost_total < comp_cost[2]) {
                    comp_cost[2] = cost_total;
                }
                for (int neighbor : adj_local[u]) {
                    if (!inS[neighbor]) {
                        pq.push({cost_local[neighbor], neighbor});
                    }
                }
                for (int neighbor : adj_local[v]) {
                    if (!inS[neighbor]) {
                        pq.push({cost_local[neighbor], neighbor});
                    }
                }
                for (int s = 3; s <= L; s++) {
                    while (!pq.empty() && inS[pq.top().second]) {
                        pq.pop();
                    }
                    if (pq.empty()) break;
                    int c = pq.top().first;
                    int node = pq.top().second;
                    pq.pop();
                    inS[node] = true;
                    cost_total += c;
                    if (cost_total < comp_cost[s]) {
                        comp_cost[s] = cost_total;
                    }
                    for (int neighbor : adj_local[node]) {
                        if (!inS[neighbor]) {
                            pq.push({cost_local[neighbor], neighbor});
                        }
                    }
                }
            }
        }

        long long new_dp[MAXN];
        for (int s = 0; s <= N; s++) {
            new_dp[s] = dp[s];
        }
        for (int s1 = 0; s1 <= N; s1++) {
            if (dp[s1] == INF) continue;
            for (int s2 = 2; s2 <= L; s2++) {
                if (comp_cost[s2] == INF) continue;
                if (s1 + s2 > N) continue;
                if (dp[s1] + comp_cost[s2] < new_dp[s1 + s2]) {
                    new_dp[s1 + s2] = dp[s1] + comp_cost[s2];
                }
            }
        }
        for (int s = 0; s <= N; s++) {
            dp[s] = new_dp[s];
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        long long S;
        cin >> S;
        int ans = 0;
        for (int s = N; s >= 0; s--) {
            if (dp[s] <= S) {
                ans = s;
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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