제출 #960733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960733		peterandvoi	도로 폐쇄 (APIO21_roads)	C++17	29 / 100	212 ms	160472 KiB

roads

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

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mxN = (int) 1e5 + 5;
const int LOG = 30;
const int NODE = mxN * LOG;
const long long INF = (long long) 1e18;

#define BIT(x, i) ((x) >> (i) & 1)

int N, K;
int node;
long long dp[mxN][2];
int deg[mxN];
bool vis[mxN], on[mxN];
int nxt[NODE][2], cnt[NODE];
long long sum[NODE];
vector<int> pos[mxN];
vector<pair<int, int>> g[mxN], graph[mxN];

void ins(int u, int x) {
    int p = u;
    for (int i = LOG - 1; i >= 0; --i) {
        int c = BIT(x, i);
        if (!nxt[p][c]) {
            nxt[p][c] = ++node;
        }
        p = nxt[p][c];
        sum[p] += x;
        cnt[p]++;
    }
}

void ers(int u, int x) {
    int p = u;
    for (int i = LOG - 1; i >= 0; --i) {
        int c = BIT(x, i);
        p = nxt[p][c];
        sum[p] -= x;
        cnt[p]--;
    }
}

long long get(int u, int k) {
    k = max(0, k);
    if (!k) {
        return 0;
    }
    long long res = 0;
    int p = u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (cnt[nxt[p][0]] >= k) {
            p = nxt[p][0];
        } else {
            k -= cnt[nxt[p][0]];
            res += sum[nxt[p][0]];
            p = nxt[p][1];
        }
    }
    return res + k * (sum[p] / cnt[p]);
}

int rt;

void dfs(int u) {
    dp[u][0] = dp[u][1] = INF;
    vis[u] = true;
    long long s = 0;
    vector<long long> delta;
    for (auto [v, w] : graph[u]) {
        if (!vis[v]) {
            dfs(v);
            delta.emplace_back(dp[v][1] - dp[v][0] + w);
            s += dp[v][0];
        }
    }
    sort(delta.begin(), delta.end());
    for (int i = 1; i < (int) delta.size(); ++i) {
        delta[i] += delta[i - 1];
    }
    int need = deg[u] - K;
    int m = (int) delta.size(), tm = deg[u] - m - (u != rt);
    for (int i = 0; i <= m; ++i) {
        if (need - 1 - i <= tm) {
            dp[u][1] = min(dp[u][1], s + (i ? delta[i - 1] : 0LL) + get(u, need - 1 - i));
        }
        if (need - i <= tm) {
            dp[u][0] = min(dp[u][0], s + (i ? delta[i - 1] : 0LL) + get(u, need - i));
        }
    }
}

vector<int> ver;

void turn_on(int u) {
    on[u] = true;
    ver.emplace_back(u);
    for (auto [v, w] : g[u]) {
        if (on[v]) {
            ers(v, w);
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        } else {
            ins(u, w);
        }
    }
}

std::vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = n;
    node = N;
    vector<long long> res(N);
    for (int i = 0; i < N - 1; ++i) {
        U[i]++;
        V[i]++;
        deg[U[i]]++;
        deg[V[i]]++;
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    for (int i = 1; i <= N; ++i) {
        pos[deg[i]].emplace_back(i);
    }
    for (int i = N - 1; i >= 0; --i) {
        K = i;
        for (int u : pos[i + 1]) {
            turn_on(u);
        }
        for (int u : ver) {
            if (!vis[u]) {
                rt = u;
                dfs(u);
                res[i] += dp[u][0];
            }
        }
        for (int u : ver) {
            vis[u] = false;
        }
    }
    return res;
}

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