oj.uz

Submission #656981

# Submission time Handle Problem Language Result Execution time Memory
656981 2022-11-08T15:56:12 Z four_specks Džumbus (COCI19_dzumbus) C++17
110 / 110
 49 ms 11416 KB 
#include <bits/stdc++.h>

using namespace std;

inline namespace
{
    template <typename T>
    bool ckmin(T &lhs, const T &rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }

    struct DSU
    {
        DSU(int n) : e(n, -1) {}

        int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
        bool same(int x, int y) { return find(x) == find(y); }

        bool unite(int x, int y)
        {
            x = find(x);
            y = find(y);

            if (x == y)
                return 0;

            if (e[x] > e[y])
                swap(x, y);

            e[x] += e[y];
            e[y] = x;

            return 1;
        }

    private:
        vector<int> e;
    };

    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

void solve(int _test_ = -1)
{
    const long INF = LONG_MAX >> 10;

    int n, m;
    cin >> n >> m;

    vector<long> a(n + 1);
    a[0] = INF;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<vector<int>> adj(n + 1);

    DSU dsu(n + 1);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
        dsu.unite(a, b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dsu.find(i) == i)
        {
            adj[0].push_back(i);
            adj[i].push_back(0);
        }
    }

    // states:
    // 0 -> not taken or taken+paired
    // 1 -> taken+alone or taken+paired
    vector dp(n + 1, vector<vector<long>>(2));
    YCombinator(
        [&](auto self, int u, int p) -> void
        {
            dp[u][0].push_back(0), dp[u][0].push_back(INF);
            dp[u][1].push_back(INF), dp[u][1].push_back(a[u]);
            for (int v : adj[u])
            {
                if (v != p)
                {
                    self(v, u);

                    int x = (int)dp[u][0].size(), y = (int)dp[v][0].size(), z = x + y - 1;
                    vector tab(2, vector<long>(z, INF));
                    for (int i = 0; i < x; i++)
                    {
                        for (int j = 0; j < y; j++)
                            ckmin(tab[0][i + j], min(dp[u][0][i] + dp[v][0][j], dp[u][1][i] + dp[v][1][j]));
                    }
                    for (int i = 0; i < x; i++)
                    {
                        for (int j = 0; j < y; j++)
                            ckmin(tab[1][i + j], dp[u][1][i] + min(dp[v][0][j], dp[v][1][j]));
                    }
                    dp[u] = move(tab);
                }
            }
        })(0, -1);

    vector<long> req = dp[0][0];
    for (int i = (int)req.size() - 2; i >= 0; i--)
        ckmin(req[i], req[i + 1]);

    int q;
    cin >> q;

    for (int z = 0; z < q; z++)
    {
        long s;
        cin >> s;

        int cnt = (int)(upper_bound(req.begin(), req.end(), s) - req.begin()) - 1;

        cout << cnt << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    int T_ = 1;
    // cin >> T_;

    for (int t_ = 0; t_ < T_; t_++)
        solve(t_);

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 9 ms 8532 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 9 ms 8532 KB Output is correct
3 Correct 43 ms 10728 KB Output is correct
4 Correct 49 ms 11416 KB Output is correct
5 Correct 47 ms 11000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2448 KB Output is correct
2 Correct 33 ms 2160 KB Output is correct
3 Correct 41 ms 2720 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 9 ms 8532 KB Output is correct
3 Correct 43 ms 10728 KB Output is correct
4 Correct 49 ms 11416 KB Output is correct
5 Correct 47 ms 11000 KB Output is correct
6 Correct 36 ms 2448 KB Output is correct
7 Correct 33 ms 2160 KB Output is correct
8 Correct 41 ms 2720 KB Output is correct
9 Correct 39 ms 3008 KB Output is correct
10 Correct 44 ms 3384 KB Output is correct
11 Correct 45 ms 3024 KB Output is correct