제출 #1256654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256654		MisterReaper	Džumbus (COCI19_dzumbus)	C++17	110 / 110	23 ms	9796 KiB

dzumbus

// File S.cpp created on 11.08.2025 at 20:22:27
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T>
inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

struct Info {
    std::vector<i64> x[3];
    Info() {}
    Info(i64 c) {
        x[0] = {0};
        x[1] = {c};
    }
};

#define sz(x) int(x.size())

inline Info operator+ (const Info& lhs, const Info& rhs) {
    Info res;
    res.x[0].assign(std::max({
        sz(lhs.x[0]) + sz(rhs.x[0]) - 1,
        sz(lhs.x[0]) + sz(rhs.x[1]) - 1,
        sz(lhs.x[0]) + sz(rhs.x[2]) - 1}), inf);
    res.x[1].assign(std::max({
        sz(lhs.x[1]) + sz(rhs.x[0]) - 1}), inf);
    res.x[2].assign(std::max({
        sz(lhs.x[1]) + sz(rhs.x[1]) + 1,
        sz(lhs.x[1]) + sz(rhs.x[2]),
        sz(lhs.x[2]) + sz(rhs.x[0]) - 1,
        sz(lhs.x[2]) + sz(rhs.x[1]),
        sz(lhs.x[2]) + sz(rhs.x[2]) - 1}), inf);
    for (int i = 0; i < lhs.x[0].size(); ++i) {
        for (int j = 0; j < rhs.x[0].size(); ++j) {
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[0][j]);
        }
        for (int j = 0; j < rhs.x[1].size(); ++j) {
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[1][j]);
        }
        for (int j = 0; j < rhs.x[2].size(); ++j) {
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[2][j]);
        }
    }
    for (int i = 0; i < lhs.x[1].size(); ++i) {
        for (int j = 0; j < rhs.x[0].size(); ++j) {
            chmin(res.x[1][i + j], lhs.x[1][i] + rhs.x[0][j]);
        }
        for (int j = 0; j < rhs.x[1].size(); ++j) {
            chmin(res.x[2][i + j + 2], lhs.x[1][i] + rhs.x[1][j]);
        }
        for (int j = 0; j < rhs.x[2].size(); ++j) {
            chmin(res.x[2][i + j + 1], lhs.x[1][i] + rhs.x[2][j]);
        }
    }
    for (int i = 0; i < lhs.x[2].size(); ++i) {
        for (int j = 0; j < rhs.x[0].size(); ++j) {
            chmin(res.x[2][i + j], lhs.x[2][i] + rhs.x[0][j]);
        }
        for (int j = 0; j < rhs.x[1].size(); ++j) {
            chmin(res.x[2][i + j + 1], lhs.x[2][i] + rhs.x[1][j]);
        }
        for (int j = 0; j < rhs.x[2].size(); ++j) {
            chmin(res.x[2][i + j], lhs.x[2][i] + rhs.x[2][j]);
        }
    }
    return res;
}

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

    int N, M;
    std::cin >> N >> M;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        int U, V;
        std::cin >> U >> V;
        --U, --V;
        adj[U].emplace_back(V);
        adj[V].emplace_back(U);
    }

    std::vector<Info> f(N);
    std::vector<int> vis(N);
    auto dfs = [&](auto&& self, int v) -> void {
        f[v] = A[v];
        vis[v] = true;
        for (auto u : adj[v]) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
            self(self, u);
            f[v] = f[v] + f[u];
            debug(v, f[v].x[0], f[v].x[1]);
        }
    };

    std::vector<i64> all = {0};
    for (int v = 0; v < N; ++v) {
        if (vis[v]) {
            continue;
        }
        dfs(dfs, v);
        std::vector<i64> nall;
        nall.assign(all.size() + std::max({f[v].x[0].size(), f[v].x[1].size(), f[v].x[2].size()}), inf);
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j < f[v].x[0].size(); ++j) {
                chmin(nall[i + j], all[i] + f[v].x[0][j]);
            }
        }
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j < f[v].x[1].size(); ++j) {
                chmin(nall[i + j], all[i] + f[v].x[1][j]);
            }
        }
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j < f[v].x[2].size(); ++j) {
                chmin(nall[i + j], all[i] + f[v].x[2][j]);
            }
        }
        all = std::move(nall);
    }

    for (int i = int(all.size()) - 2; i >= 0; --i) {
        chmin(all[i], all[i + 1]);
    }

    debug(all);

    int Q;
    std::cin >> Q;

    while (Q--) {
        int S;
        std::cin >> S;

        int res = std::upper_bound(all.begin(), all.end(), S) - all.begin();
        std::cout << res - 1 << '\n';
    }

    return 0;
}

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