Submission #910020

#	Time	Username	Problem	Language	Result	Execution time	Memory
910020		pragmatist	Road Closures (APIO21_roads)	C++17	53 / 100	2087 ms	27920 KiB

roads

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;
const long long INF = (long long)1e18 + 7;
const long long oo = (long long)1e15 + 7;
const int inf = (int)1e9 + 7;

int n, K, deg[N];
bool used[N];
long long dp[N][2];
vector<pair<int, int> > g[N];

bool cmp(pair<int, int> i, pair<int, int> j) {
    return deg[i.first] > deg[j.first];
}

long long ans, old[N];

void dfs(int v, int pr, int last) {
    for(auto [to, w] : g[v]) {
        if(to == pr) {
            continue;
        }
        dfs(to, v, w);
    }
    long long tot = 0;
    vector<long long> cur;
    for(auto [to, w] : g[v]) {
        if(to == pr) {
            continue;
        }
        tot += dp[to][1];
        cur.push_back(dp[to][0]-dp[to][1]);
    }
    sort(cur.begin(), cur.end());
    dp[v][1] = tot+last;
    if(K+(v == pr)) {
        dp[v][0] = tot;
        for(int i = 0; i < min((int)cur.size(), K); ++i) {
            if(cur[i] > oo) {
                break;
            }
            tot += cur[i];
            if(i < K+(v == pr)-1) {
                dp[v][0] = min(dp[v][0], tot);
            }
            dp[v][1] = min(dp[v][1], tot+last);
        }
    } else {
        dp[v][0] = INF;
    }
}

void dfs(int v, int pr) {
    used[v] = 1;
    int i = 0;
    for(auto [to, w] : g[v]) {
        i++;
        if(to == pr) {
            continue;
        }
        if(deg[to] <= K) {
            break;
        }
        if(deg[to] > K) {
            dfs(to, v);
        }
    }
    int need = max(0, deg[v]-K);
    ans += need;
    if(deg[v] > K && pr != -1) {
        deg[pr]--;
    }
}

vector<long long> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
    n = _N;
    bool ok = 1;
    bool ko = 1;
    bool kk = 1;
    long long tt = 0;
    for(int i = 0; i < n-1; ++i) {
        int u = _U[i];
        int v = _V[i];
        int w = _W[i];
        tt += w;
        ko &= (u == 0);
        ok &= (w == 1);
        kk &= (u == i && v == i+1);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    if(ko) {
        sort(_W.rbegin(), _W.rend());
        vector<long long> sos;
        for(int i = 0; i < n; ++i) {
            sos.push_back(tt);
            if(i < n-1) {
                tt -= _W[i];
            }
        }
        return sos;
    }
    if(!ok) {
        vector<long long> sos;
        for(int k = 0; k < n; ++k) {
            if(kk && k > 2) {
                sos.push_back(0);
                continue;
            }
            K = k;
            dfs(0, 0, inf);
            sos.push_back(dp[0][0]);
        }
        return sos;
    }
    for(int i = 0; i < n; ++i) {
        deg[i] = (int)g[i].size();
        old[i] = deg[i];
    }
    vector<long long> po;
    vector<pair<int, int> > o;
    for(int i = 0; i < n; ++i) {
        sort(g[i].begin(), g[i].end(), cmp);
        o.push_back({deg[i], i});
    }
    sort(o.rbegin(), o.rend());
    for(int k = 0; k <  n; ++k) {
        K = k;
        vector<int> bad;
        for(auto [x, y] : o) {
            if(x <= k) {
                break;
            }
            bad.push_back(y);
        }
        ans = 0;
        for(auto x : bad) {
            if(!used[x]) {
                dfs(x, -1);
            }
        }
        for(auto x : bad) {
            deg[x] = old[x];
            used[x] = 0;
        }
        po.push_back(ans);
    }
    return po;
}

• 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