Submission #561728

#	Time	Username	Problem	Language	Result	Execution time	Memory
561728		piOOE	Road Closures (APIO21_roads)	C++17	53 / 100	570 ms	33512 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;

const int N = 100001;
int A[N], B[N], W[N], n;
vector<int> gr[N];
vector<pair<int, int>> g[N];

vector<ll> minimum_closure_costs(int nn, vector<int> uu, vector<int> vv, vector<int> ww) {
    n = nn;
    for (int i = 0; i < n - 1; ++i) {
        A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
    }
    vector<ll> ans(n);
    if (*max_element(all(W)) == 1) {
        vector<int> pp(n), cnt(n), depth(n);
        vector<bool> used(n);
        function<void(int, int)> dfs = [&](int v, int p) {
            pp[v] = p;
            for (int to: gr[v]) {
                if (to != p) {
                    depth[to] = depth[v] + 1;
                    dfs(to, v);
                }
            }
        };
        for (int i = 0; i < n - 1; ++i) {
            gr[A[i]].push_back(B[i]);
            gr[B[i]].push_back(A[i]);
        }
        vector<int> ord(n);
        iota(all(ord), 0);
        sort(all(ord), [](int i, int j) {
            return gr[i].size() > gr[j].size();
        });
        dfs(0, -1);
        for (int k = 0; k < n; ++k) {
            vector<int> now;
            for (int i: ord) {
                if (gr[i].size() <= k) break;
                now.push_back(i);
                used[i] = true;
                cnt[i] = (int) gr[i].size();
            }
            sort(all(now), [&depth](int i, int j) {
                return depth[i] > depth[j];
            });
            for (int i: now) {
                if (pp[i] != -1 && used[pp[i]] && cnt[i] > k) {
                    --cnt[pp[i]];
                    --cnt[i];
                    ++ans[k];
                }
            }
            for (int i: now) {
                ans[k] += max(0, cnt[i] - k);
                used[i] = false;
            }
        }
        return ans;
    } else if (n <= 2000) {
        for (int i = 0; i < n - 1; ++i) {
            g[A[i]].emplace_back(B[i], W[i]);
            g[B[i]].emplace_back(A[i], W[i]);
        }
        for (int k = 0; k < n; ++k) {
            vector<vector<ll>> dp(n + 1, vector<ll>(2));
            function<void(int, int)> dfs = [&](int v, int p) {
                vector<pair<int, int>> adj;
                for (auto [to, w]: g[v]) {
                    if (to != p) {
                        dfs(to, v);
                        adj.emplace_back(to, w);
                    }
                }
                if (k > (int) size(adj)) {
                    vector<ll> nw;
                    ll ans = 0;
                    for (auto [to, w]: adj) {
                        ans += dp[to][0] + w;
                        nw.push_back(dp[to][1] - dp[to][0] - w);
                    }
                    sort(all(nw));
                    for (int i = 0; i < (int) size(nw); ++i) {
                        if (nw[i] < 0)
                            ans += nw[i];
                    }
                    dp[v][1] = dp[v][0] = ans;
                } else {
                    vector<ll> nw;
                    ll ans = 0;
                    for (auto [to, w]: adj) {
                        ans += dp[to][0] + w;
                        nw.push_back(dp[to][1] - dp[to][0] - w);
                    }
                    sort(all(nw));
                    ll added = 0;
                    for (int i = 0; i < k - 1; ++i) {
                        if (nw[i] < 0)
                            added += nw[i];
                    }
                    dp[v][1] = ans + added;
                    added = 0;
                    for (int i = 0; i < k; ++i) {
                        added += nw[i];
                    }
                    dp[v][0] = min(dp[v][1], ans + added);
                }
            };
            dfs(0, -1);
            ans[k] = dp[0][0];
        }
        return ans;
    } else if (*max_element(all(A)) == 0) {
        sort(W, W + n - 1);
        ll nw = 0;
        ll sum = accumulate(all(W), 0ll);
        for (int k = 0; k < n; ++k) {
            if (k) nw += W[n - k - 1];
            ans[k] = sum - nw;
        }
        return ans;
    } else {
        for (int i = 0; i < n - 1; ++i) {
            g[A[i]].emplace_back(B[i], W[i]);
            g[B[i]].emplace_back(A[i], W[i]);
        }
        ans[0] = accumulate(all(W), 0ll);
        for (int k = 1; k <= 1; ++k) {
            vector<vector<ll>> dp(n + 1, vector<ll>(2));
            function<void(int, int)> dfs = [&](int v, int p) {
                vector<pair<int, int>> adj;
                for (auto [to, w]: g[v]) {
                    if (to != p) {
                        dfs(to, v);
                        adj.emplace_back(to, w);
                    }
                }
                if (k > (int) size(adj)) {
                    vector<ll> nw;
                    ll ans = 0;
                    for (auto [to, w]: adj) {
                        ans += dp[to][0] + w;
                        nw.push_back(dp[to][1] - dp[to][0] - w);
                    }
                    sort(all(nw));
                    for (int i = 0; i < (int) size(nw); ++i) {
                        if (nw[i] < 0)
                            ans += nw[i];
                    }
                    dp[v][1] = dp[v][0] = ans;
                } else {
                    vector<ll> nw;
                    ll ans = 0;
                    for (auto [to, w]: adj) {
                        ans += dp[to][0] + w;
                        nw.push_back(dp[to][1] - dp[to][0] - w);
                    }
                    sort(all(nw));
                    ll added = 0;
                    for (int i = 0; i < k - 1; ++i) {
                        if (nw[i] < 0)
                            added += nw[i];
                    }
                    dp[v][1] = ans + added;
                    added = 0;
                    for (int i = 0; i < k; ++i) {
                        added += nw[i];
                    }
                    dp[v][0] = min(dp[v][1], ans + added);
                }
            };
            dfs(0, -1);
            ans[k] = dp[0][0];
        }
        for (int k = 2; k < n; ++k) {
            ans[k] = 0;
        }
        return ans;
    }
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:47:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |                 if (gr[i].size() <= k) break;
      |                     ~~~~~~~~~~~~~^~~~

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