Submission #489775

#	Time	Username	Problem	Language	Result	Execution time	Memory
489775		dung11112003	Road Closures (APIO21_roads)	C++11	22 / 100	199 ms	45776 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

using namespace std;

vector <long long> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W)
{
    int n = N;
    vector <vector <array <int, 3>>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u = U[i], v = V[i], w = W[i];
        adj[u].push_back({v, w, 0});
        adj[v].push_back({u, w, 0});
    }
    struct FenwickTree
    {
        //1 - indexed
        int n;
        vector <int> f;
        vector <long long> g;
        FenwickTree () : n(0), f(), g() {};
        FenwickTree (int n) : n(n), f(n + 1), g(n + 1) {};
        void insert(int x, long long d)
        {
            for (; x <= n; x += x & -x)
            {
                f[x]++;
                g[x] += d;
            }
        }
        int size()
        {
            int x = n, sum = 0;
            for (; x; x &= x - 1)
            {
                sum += f[x];
            }
            return sum;
        }
        long long prefix_kth(int k)
        {
            int idx = 0;
            long long sum = 0;
            for (int mask = 1 << 20; mask; mask >>= 1)
            {
                if (idx + mask <= n && f[idx + mask] <= k)
                {
                    idx += mask;
                    k -= f[idx];
                    sum += g[idx];
                }
            }
            return sum;
        }
    };
    vector <FenwickTree> f(n);
    for (int i = 0; i < n; i++)
    {
        sort(adj[i].begin(), adj[i].end(), [](const array <int, 3> &x, const array <int, 3> &y)
        {
            return x[1] < y[1];
        });
        f[i] = FenwickTree(adj[i].size());
        for (int j = 0; j < (int)adj[i].size(); j++)
        {
            adj[i][j][2] = j + 1;
        }
    }
    vector <int> sorted_deg(n);
    iota(sorted_deg.begin(), sorted_deg.end(), 0);
    sort(sorted_deg.begin(), sorted_deg.end(), [&](int x, int y)
    {
        return adj[x].size() < adj[y].size();
    });
    vector <int> erased(n);
    set <int> not_erased;
    vector <int> flag(n);
    for (int i = 0; i < n; i++)
    {
        not_erased.insert(i);
    }
    int id = 0;
    vector <array <long long, 2>> dp(n);
    vector <long long> ans(n);
    const long long inf = 1e18;
    ans[0] = accumulate(W.begin(), W.end(), 0LL);
    vector <int> deg(n);
    for (int i = 0; i < n; i++)
    {
        deg[i] = (int)adj[i].size();
    }
    for (int k = 1; k < n; k++)
    {
        vector <int> pending;
        while (id < n && (int)deg[sorted_deg[id]] <= k)
        {
            int u = sorted_deg[id];
            //remove u
            for (auto &e: adj[u])
            {
                pending.push_back(e[0]);
            }
            erased[u] = 1;
            not_erased.erase(u);
            adj[u].clear();
            id++;
        }
        sort(pending.begin(), pending.end());
        pending.resize(unique(pending.begin(), pending.end()) - pending.begin());
        for (auto &u: pending)
        {
            vector <array <int, 3>> new_adj;
            for (auto &e: adj[u])
            {
                int v = e[0];
                if (erased[v])
                {
                    f[u].insert(e[2], e[1]);
                }
                else
                {
                    new_adj.push_back(e);
                }
            }
            adj[u].swap(new_adj);
        }
        function <void (int)> dfs([&](int u)
        {
            flag[u] = 1;
            dp[u][0] = dp[u][1] = inf;
            long long sum[2] = {};
            vector <long long> vec;
            for (auto &e: adj[u])
            {
                int v = e[0], w = e[1];
                if (!flag[v])
                {
                    dfs(v);
                    sum[0] += dp[v][0];
                    sum[1] += dp[v][0];
                    vec.push_back(dp[v][1] + w - dp[v][0]);
                }
            }
            sort(vec.begin(), vec.end());
            partial_sum(vec.begin(), vec.end(), vec.begin());
            int need = (int)deg[u] - k, cnt = f[u].size();
            if (cnt >= need)
            {
                dp[u][0] = min(dp[u][0], f[u].prefix_kth(need) + sum[0]);
            }
            if (cnt >= need - 1)
            {
                dp[u][1] = min(dp[u][1], f[u].prefix_kth(need - 1) + sum[1]);
            }
            for (int i = 0; i < (int)vec.size(); i++)
            {
                if (cnt + i + 1 >= need && i + 1 <= need)
                {
                    dp[u][0] = min(dp[u][0], sum[0] + vec[i] + f[u].prefix_kth(need - i - 1));
                }
                if (cnt + i + 1 >= need - 1 && i + 1 <= need - 1)
                {
                    dp[u][1] = min(dp[u][1], sum[1] + vec[i] + f[u].prefix_kth(need - 1 - i - 1));
                }
            }
        });
        for (auto &u: not_erased)
        {
            if (!flag[u])
            {
                dfs(u);
                ans[k] += dp[u][0];
            }
        }
        for (auto &u: not_erased)
        {
            flag[u] = 0;
        }
    }
    return ans;
}

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