Submission #562145

#	Time	Username	Problem	Language	Result	Execution time	Memory
562145		piOOE	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	224 ms	55328 KiB

roads

#include "roads.h"

//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

struct fenwick {
    vector<ll> t;
    int n;

    fenwick() = default;

    fenwick(int x) {
        n = x + 1;
        t.assign(n, 0);
    }

    void init(int x) {
        n = x + 1;
        t.assign(n, 0);
    }

    void add(int i, int x) {
        i += 1;
        for (; i < n; i += i & -i)
            t[i] += x;
    }

    ll get(int i) {
        ll ans = 0;
        i += 1;
        i = min(n - 1, i);
        for (; i > 0; i -= i & -i)
            ans += t[i];
        return ans;
    }


    int kth(int k) {
        if (k == 0) return -1;
        int i = 0;
        for (int j = 18; j > -1; --j) {
            if (i + (1 << j) < n && t[i + (1 << j)] < k) {
                i += (1 << j);
                k -= t[i];
            }
        }
        return i;
    }
};

const int N = 100001;
int A[N], B[N], W[N], n, par[N], sz[N], wp[N], depth[N];
vector<pair<int, int>> g[N], gr[N];
fenwick f1[N], f2[N];
bool used[N];

ll dp[2][N], sm[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; ++i) {
        gr[i].clear(), g[i].clear();
        sm[i] = 0;
    }
    for (int i = 0; i < n - 1; ++i) {
        A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
        gr[A[i]].emplace_back(-W[i], B[i]);
        gr[B[i]].emplace_back(-W[i], A[i]);
    }
    for (int i = 0; i < n; ++i) {
        sort(all(gr[i]));
        sz[i] = (int) size(gr[i]);
        f1[i].init(sz[i]);
        f2[i].init(sz[i]);
    }
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [](int i, int j) {
        return sz[i] > sz[j];
    });
    function<void(int, int, int)> prec = [&prec](int v, int p, int wep) {
        par[v] = p;
        wp[v] = wep;
        for (auto [w, to]: gr[v]) {
            if (to != p) {
                depth[to] = depth[v] + 1;
                prec(to, v, -w);
            }
        }
    };
    vector<ll> ans(n);
    prec(0, -1, 0);
    for (int k = 0; k < n; ++k) {
        vector<int> now;
        for (int i: ord) {
            if (sz[i] < k) break;
            if (sz[i] == k) {
                for (auto [w, to]: gr[i]) {
                    if (sz[to] <= sz[i]) continue;
                    int id = lower_bound(all(gr[to]), make_pair(w, i)) - begin(gr[to]);
                    assert(id < sz[to] && gr[to][id] == make_pair(w, i));
                    f1[to].add(id, 1);
                    f2[to].add(id, -w);
                    sm[to] += -w;
                }
                continue;
            }
            now.push_back(i);
            used[i] = true;
        }
        for (int x: now) {
            if (par[x] != -1 && used[par[x]]) {
                g[par[x]].emplace_back(x, wp[x]);
            }
        }
        const ll infL = 3e18;
        for (int x: now) used[x] = false;
        function<void(int, int)> dfs = [&](int v, int p) {
            used[v] = true;
            vector<pair<int, int>> adj;
            for (auto [to, w]: g[v]) {
                if (to != p) {
                    dfs(to, v);
                    adj.emplace_back(to, w);
                }
            }
            vector<ll> nw;
            ll sum = 0;
            for (auto [to, w]: adj) {
                nw.push_back(dp[1][to] - dp[0][to] - w);
                sum += dp[0][to] + w;
            }
            sort(all(nw));
            dp[1][v] = dp[0][v] = infL;
            for (int take = 0; take <= min(k, (int) size(nw)); ++take) {
                if (take) {
                    sum += nw[take - 1];
                }
                if (take < k) {
                    int id = f1[v].kth(k - take - 1);
                    ll added = sm[v] - f2[v].get(id);
                    dp[1][v] = min(dp[1][v], sum + added);
                }
                int id = f1[v].kth(k - take);
                ll added = sm[v] - f2[v].get(id);
                dp[0][v] = min(dp[0][v], sum + added);
            }
            dp[0][v] = min(dp[0][v], dp[1][v]);
        };
        sort(all(now), [](int i, int j) {
            return depth[i] < depth[j];
        });
        for (int v: now) {
            if (!used[v]) {
                dfs(v, -1);
                assert(dp[0][v] != infL);
                ans[k] += dp[0][v];
            }
        }
        for (int v: now) {
            used[v] = false;
            g[v].clear();
        }
    }
    return ans;
}

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