oj.uz

Submission #516706

# Submission time Handle Problem Language Result Execution time Memory
516706 2022-01-22T01:32:47 Z KoD Džumbus (COCI19_dzumbus) C++17
110 / 110
 61 ms 3348 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

using i64 = std::int64_t;
constexpr i64 inf = std::numeric_limits<i64>::max() / 2;

void setmin(i64& x, const i64 y) {
    if (x > y) {
        x = y;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> S(N);
    for (auto& x : S) {
        std::cin >> x;
    }
    vector<vector<int>> graph(N);
    while (M--) {
        int a, b;
        std::cin >> a >> b;
        a -= 1, b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<char> done(N);
    vector<i64> all = {0};
    for (int root = 0; root < N; ++root) {
        if (done[root]) {
            continue;
        }
        const auto result = rec_lambda([&](auto&& dfs, const int u) -> vector<array<i64, 3>> {
            done[u] = true;
            vector<array<i64, 3>> dp(2);
            for (auto& a : dp) {
                a.fill(inf);
            }
            dp[0][0] = 0;
            dp[0][1] = S[u];
            for (const int v : graph[u]) {
                if (done[v]) {
                    continue;
                }
                const auto add = dfs(v);
                const int n = dp.size(), m = add.size();
                vector<array<i64, 3>> next(n + m - 1);
                for (auto& a : next) {
                    a.fill(inf);
                }
                for (int i = 0; i < n; ++i) {
                    for (int k = 0; k < 3; ++k) {
                        if (dp[i][k] == inf) {
                            continue;
                        }
                        for (int j = 0; j < m; ++j) {
                            for (int l = 0; l < 3; ++l) {
                                if (add[j][l] == inf) {
                                    continue;
                                }
                                const int nk = (k == 1 and l >= 1 ? 2 : k);
                                const int nl = (l == 1 and k >= 1 ? 2 : l);
                                setmin(next[i + j + (nk - k) + (nl - l)][nk], dp[i][k] + add[j][l]);
                            }
                        }
                    }
                }
                dp = std::move(next);
            }
            return dp;
        })(root);
        const int n = all.size(), m = result.size();
        vector<i64> next(n + m - 1, inf);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                setmin(next[i + j], all[i] + std::min({result[j][0], result[j][1], result[j][2]}));
            }
        }
        all = std::move(next);
    }
    for (int i = N; i > 0; --i) {
        setmin(all[i - 1], all[i]);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        i64 x;
        std::cin >> x;
        std::cout << std::upper_bound(all.begin(), all.end(), x) - all.begin() - 1 << '\n';
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 576 KB Output is correct
2 Correct 13 ms 628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 576 KB Output is correct
2 Correct 13 ms 628 KB Output is correct
3 Correct 45 ms 2744 KB Output is correct
4 Correct 61 ms 3348 KB Output is correct
5 Correct 49 ms 2864 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2376 KB Output is correct
2 Correct 31 ms 2120 KB Output is correct
3 Correct 33 ms 2588 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 576 KB Output is correct
2 Correct 13 ms 628 KB Output is correct
3 Correct 45 ms 2744 KB Output is correct
4 Correct 61 ms 3348 KB Output is correct
5 Correct 49 ms 2864 KB Output is correct
6 Correct 33 ms 2376 KB Output is correct
7 Correct 31 ms 2120 KB Output is correct
8 Correct 33 ms 2588 KB Output is correct
9 Correct 34 ms 2392 KB Output is correct
10 Correct 38 ms 3144 KB Output is correct
11 Correct 37 ms 2880 KB Output is correct