Submission #960720

#	Time	Username	Problem	Language	Result	Execution time	Memory
960720		peterandvoi	Road Closures (APIO21_roads)	C++17	0 / 100	212 ms	119336 KiB

roads

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

using namespace std;

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

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

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

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

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

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

long long get(long long u, long long k) {
    if (!k) {
        return 0;
    }
    long long res = 0;
    long long p = u;
    for (long long 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]);
}

long long rt;

void dfs(long long 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 (long long i = 1; i < (long long) delta.size(); ++i) {
        delta[i] += delta[i - 1];
    }
    long long need = deg[u] - K;
    long long m = (long long) delta.size(), tm = deg[u] - m - (u != rt);
    for (long long i = 0; i <= min(m, need); ++i) {
        if (i <= need - 1 && 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<long long> ver;

void turn_on(long long 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 (long long i = 0; i < N; ++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 (long long i = 1; i <= N; ++i) {
        pos[deg[i]].emplace_back(i);
    }
    for (long long i = N - 1; i >= 0; --i) {
        K = i;
        for (long long u : pos[i + 1]) {
            turn_on(u);
        }
        for (long long u : ver) {
            if (!vis[u]) {
                rt = u;
                dfs(u);
                res[i] += dp[u][0];
            }
        }
        for (long long u : ver) {
            vis[u] = false;
        }
    }
    return res;
}

• Subtask 1: 0 / 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