Submission #603397

#	Time	Username	Problem	Language	Result	Execution time	Memory
603397		KoD	Road Closures (APIO21_roads)	C++17	5 / 100	281 ms	36444 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using ll = long long;
using std::array;
using std::pair;
using std::vector;

constexpr ll inf = std::numeric_limits<ll>::max() / 2;

template <class T>
int lowb(const vector<T>& vec, const T& x) {
    return std::lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

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

template <class T> class fenwick {
    int size, pow2;
    vector<T> data;

  public:
    fenwick() = default;

    explicit fenwick(const int n) : size(n), data(n + 1) {
        pow2 = 1;
        while (pow2 <= size) {
            pow2 <<= 1;
        }
    }

    void add(int i, const T& x) {
        i += 1;
        while (i <= size) {
            data[i] += x;
            i += i & -i;
        }
    }

    T pref(int i) const {
        T ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }

    T fold(const int l, const int r) const {
        return pref(r) - pref(l);
    }

    template <class F> pair<int, T> satisfies(const F& f) const {
        int i = 0;
        T sum = 0;
        for (int d = pow2; (d >>= 1) > 0;) {
            if (i + d <= size and f(sum + data[i + d])) {
                i += d;
                sum += data[i];
            }
        }
        return {i, sum};
    }
};

class multiset {
    vector<int> data;
    fenwick<int> count;
    fenwick<ll> sum;

  public:
    multiset() = default;

    explicit multiset(const vector<int>& vec) {
        data = vec;
        std::sort(data.begin(), data.end());
        data.erase(std::unique(data.begin(), data.end()), data.end());
        const int n = (int)data.size();
        count = fenwick<int>(n);
        sum = fenwick<ll>(n);
        for (const int x : vec) {
            const int i = lowb(data, x);
            count.add(i, 1);
            sum.add(i, x);
        }
    }

    void erase(const int x) {
        const int i = lowb(data, x);
        count.add(i, -1);
        sum.add(i, -x);
    }

    ll pref(const int n) const {
        const auto [i, k] = count.satisfies([&](const int x) { return x <= n; });
        return sum.pref(i) + (k == n ? 0 : (ll)data[i] * (n - k));
    }
};

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        graph[U[i]].push_back(i);
        graph[V[i]].push_back(i);
    }
    vector<int> pedge(N, -1), depth(N);
    fixed([&](auto&& dfs, const int u) -> void {
        for (const int e : graph[u]) {
            if (e != pedge[u]) {
                const int v = U[e] ^ V[e] ^ u;
                pedge[v] = e;
                depth[v] = depth[u] + 1;
                dfs(v);
            }
        }
    })(0);
    vector<int> list;
    vector<vector<int>> deglist(N);
    vector<multiset> alive(N);
    vector<vector<int>> dead(N);
    vector<array<ll, 2>> dp(N);
    vector<ll> ret(N);
    for (int i = 0; i < N; ++i) {
        deglist[(int)graph[i].size() - 1].push_back(i);
        vector<int> tmp;
        for (const int e : graph[i]) {
            if (e != pedge[i]) {
                tmp.push_back(W[e]);
            }
        }
        alive[i] = multiset(tmp);
    }
    for (int d = N - 1; d > 0; --d) {
        for (const int u : deglist[d]) {
            list.push_back(u);
            if (const int e = pedge[u]; e != -1) {
                const int v = U[e] ^ V[e] ^ u;
                alive[v].erase(W[e]);
                dead[v].push_back(e);
            }
        }
        std::sort(list.begin(), list.end(), [&](const int i, const int j) {
            return depth[i] > depth[j];
        });
        for (const int u : list) {
            const int m = (int)graph[u].size() - d;
            const int k = (int)dead[u].size();
            vector<ll> cost(k);
            for (int i = 0; i < k; ++i) {
                const int e = dead[u][i];
                const int v = U[e] ^ V[e] ^ u;
                cost[i] = std::min<ll>(W[e], dp[v][1]);
            }
            vector<ll> pref(k + 1);
            for (int i = 0; i < k; ++i) {
                pref[i + 1] = pref[i] + cost[i];
            }
            dp[u].fill(inf);
            for (int i = 0; i <= std::min(m, k); ++i) {
                dp[u][0] = std::min(dp[u][0], pref[i] + alive[u].pref(m - i));
            }
            ret[d] += dp[u][0];
            if (const int e = pedge[u]; e != -1) {
                for (int i = 0; i <= std::min(m - 1, k); ++i) {
                    dp[u][1] = std::min(dp[u][1], pref[i] + alive[u].pref(m - i - 1) + W[e]);
                }
                dp[u][1] -= dp[u][0];
                if ((int)graph[U[e] ^ V[e] ^ u].size() <= d) {
                    ret[d] += std::min<ll>(0, dp[u][1]);
                }
            }
        }
        std::cerr << std::endl;
    }
    ret[0] = std::accumulate(W.begin(), W.end(), 0ll);
    return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22